Find 4 numbers that satisfies any sum equation with a given number

I have four integer numbers a, b, c, d, and integer x ϵ [1, 40].

How do I find the values of {a, b, c, d}, for which one of following equations is true for any 1 <= x <= 40?

x = a or
x = b or
x = a + b or
x = a + b + c + d or
x + a = c + d or
x + a + b = c + d or
...
x + a + b + c = d or ... 

Example:

开发者_运维问答If x = 17, by {a = 1, b = 2, c = 5, d = 15}, I can write x + a + b = c + d

The question is to present any x ϵ [1, 40] by {a, b, c, d}.

Update:

There is only one solution, I'm sure, and I think, that

{a = 1; a + b + c + d = 40}

---

Actually here is nothing connected with programming. It is a pure mathematics. The algorithm of solving such tasks is simple. Starting from 1 we take the next biggest value possible so, that we can get all the other numbers up to sum(1..it) using only + and -.

So the first is 1.

The second will be 3, as 1 = 1, 2 = 3 - 1, 3 = 3, 4 = 3 + 1.

The 3rd is 9.

And you see the coincidence every next number id 3x previous. The four numbers you are looking for are {1, 3, 9, 27}, and you can get any number between 1 and 1 + 3 + 9 + 27 = 40 with them.

---

This is actually a case of balanced ternary location. For each of a, b, c, and d, you can either add it to the total, subtract it (because x + a + b == c + d is exactly the same as x == c + d - a - b, or leave it out. The numbers you want are therefore the ternary digit values, or 1, 3, 9, and 27.

---

This is called the set partition and kinda subset sum problem which are NP Complete problems. i.e: this is a hard problem and your best bet is to use a brute force approach or a dynamic programming approach. in either case there is no "efficient" algorithm to solve this in linear time. at least no one knows for now.

http://en.wikipedia.org/wiki/Partition_problem

http://en.wikipedia.org/wiki/Subset_sum_problem

It might be related to game theory, but still this is a NP problem.