# Fast algorithm for finding all solutions of simple equation involving only addition of terms from list

I have a list $$X=\{n_1,n_2,n_3,n_4, \dots, n_i\}$$ with $$n_i \in \mathbb{C}$$, an integer $$m \in \mathbb{N}$$ and $$S \in \mathbb{C}$$. My question is how to find all solution to the equation

$$\sum_{j=1}^m x_j=S$$ in an efficient way with Mathematica?

An example:

X={1,1/2,0,-1/2,-1};
m=3;
S=1;


I want a function combinations[X,m,S] which returns

combinations[X,m,S]
{{1,3,3},{3,1,3},{3,3,1},{1,2,4},{1,4,2},{2,1,4},{4,1,2},{2,4,1},{4,2,1},{1,1,5},{1,5,1},{5,1,1},{2,2,3},{2,3,2},{3,2,2}}


where each triple gives the index to X. For example, {1,3,3} stands for

$$S=x_1+x_3+x_3=1+0+0=1.$$

The solution I have is very slow and takes a lot of memory: I perform m tensor-products of $$X$$, creating a $$M=i \otimes i \otimes \dots \otimes i$$ matrix (with dimension of $$d(M)=i^m$$, and sum each entry. Unfortunatly, the matrix M grows exponentially, and is unfeasible even for small $$m$$ below 20.

1) Do you know a more efficient solution for finding all solutions of the equation above?

2) Do you know a more efficient solution for finding all solutions of the equation above, for the special cases of $$S=0$$ and $$S=1$$?

• This isn't exactly the subset sum problem, but dynamic programming seems like the answer. Jul 21, 2019 at 16:40
• IntegerPartitions[S, {m}, X] and post-process (Permutations)?
– kglr
Jul 21, 2019 at 16:44
• @kglr wow I was trying IntegerPartitions before and couldnt get it work, i didnt know about the third argument. It works for rational numbers, that is already really cool, thanks! Could this be extended to complex values? (at least for question 2?) Thaanks!! Jul 21, 2019 at 16:52

For rational $$n_i$$ and $$S$$, you can use IntegerPartitions:

X = {1, 1/2, 0, -1/2, -1};
m = 3;
S = 1;

posIndex=PositionIndex[X];

Flatten /@ Map[posIndex, Join @@ (Permutations /@ IntegerPartitions[S, {m}, X]), {-1}]


{{5, 1, 1}, {1, 5, 1}, {1, 1, 5}, {4, 2, 1}, {4, 1, 2}, {2, 4, 1}, {2,1, 4}, {1, 4, 2}, {1, 2, 4}, {3, 3, 1}, {3, 1, 3}, {1, 3, 3}, {3, 2, 2}, {2, 3, 2}, {2, 2, 3}}

• Very beautiful application of IntegerPartitions. As complex numbers can be interpreted as 2dimensional real numbers, would it be possible to modify your code to also cover complex rational X and S? Thanks! Jul 21, 2019 at 17:11
• Thank you @NicoDean. For complex X and S with rational real and imaginary parts, I think we can use MapThread[IntegerPartitions[#, {m},#2]& , {ReIm @ S,Transpose[ReIm @ X]}] to get the core part. Of course, because we are using Permutations m has to be small.
– kglr
Jul 21, 2019 at 17:28
• I think I understand what you try to do with ReIm. I tried now for some time but unfortunatly I cannot get it running. So in case that it is clear for you how to continue from there, could you maybe give some more hints? Otherwise i will try further myself. Thanks Jul 21, 2019 at 18:54
• @NicoDean, sorry --- we need to change Transpose[ReIm @ X] to se[ReIm/ @ X] (or better to ReIm@X).
– kglr
Jul 21, 2019 at 19:37

Could use Solve.

The example in question:

xvals = {1, 1/2, 0, -1/2, -1};
m = 3;
ss = 1;


Set up the equations and inequalities that need to be enforced.

vars = Array[n, Length[xvals]];
constraints =
Flatten[{Total[vars] - m == 0, vars.xvals - ss == 0,