# 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. – lirtosiast Jul 21 '19 at 16:40
• IntegerPartitions[S, {m}, X] and post-process (Permutations)? – kglr Jul 21 '19 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!! – Mario Krenn Jul 21 '19 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! – Mario Krenn Jul 21 '19 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 '19 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 – Mario Krenn Jul 21 '19 at 18:54
• @NicoDean, sorry --- we need to change Transpose[ReIm @ X] to se[ReIm/ @ X] (or better to ReIm@X). – kglr Jul 21 '19 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,