
Sum Subsets
Hi everyone, first time on this forum and I'm thrilled. I was wondering if anyone could perhaps show me where I can find an article, formula, book, etc, that tells me what I want to find below.
You have a number n and a list of numbers. I want to generate all the different combinations from the list that add up the n.
Example.
n = 4;
list = [1,2]
Combination 1: 1 + 1 + 1 + 1 = 4
Combination 2: 1 + 1 + 2 = 4
Combination 3: 2 + 2 = 4
There are 3 different combinations that sum up to 4 from the given list.
n = 6
list = [1,3,6]
Combination 1: 1+1+1+1+1+1 = 6
Combination 2: 1+1+1+3 = 6
Combination 3: 3+3 = 6
Combination 4: 6=6
There are 4 different combinations that sum up to 6 from the given list.
Is there an algorithm or something that I can use in a java program that will accomplish this?
Thank you.

Re: Sum Subsets
A desired combination isn't a set, because you need to include repetition. Instead call it a finite sequence in A = Seq(A).
We won't care about the ordering, even though calling it a sequence does naturally includes ordering. No problem.
If a and b are such finite sequences in A, call a*b the combined sequence of "first do a, then do b"
Ex: Let A = {1, 2, 5} and a,b in Seq(A) given by a(1) = 1, a(2) = 1, a(3) = 5, and b(1) = 5, b(2) = 2.
Then a*b = Seq(A) is given by (a*b)(1) = 1, (a*b)(2) = 1, (a*b)(3) = 5, and (a*b)(4) = 5, (a*b)(5) = 2.
For completeness, assume 0 is not allowed in A, and "{after the sequence is done", all the sequence values are 0.
Then a*b is redefined by "b starts replacing the 1st occurance of 0 in a"
This is all mumbomubo, just for precision's sake.
It's really just that a is a finite "subset" of A, except repetition is allowed. And a*b is just "a union b", except tracking repetitions.
Definition: If , define , and .
Definition: Call that special k in the above definition (length of a).
Definition: If , define by for , and for .
Definition: If , define by . Similarly for .
Define: for all .
Definition: If , define by , and for .
Definition: Let .
All that overhead crap is for a very simple recursive algorithm:

The meaning of that is "the combinations of A that sum to n" is the union over every k in A of "the combinations of A that sum to nk, and then include k".