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.