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 ... 

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}.


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( 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.

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

Need Your Help

Spring unit tests - loading different config file for different unit tests

java spring unit-testing

I have a class (ConfigurationReaderUtil) that loads an XML config file to beans (with the simpleframework). There is an other class (let's name it as XXX class) that uses the beans that are loaded ...

Single Value Decomposition implementation C++

c++ algorithm opencv

Who can recommend a stable and correct implementation Single Value Decomposition (SVD) in C++? Preferably standalone implementation (would not want to add large library for one method).