
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 $\displaystyle A \subset \mathbb{Z}^+$, define $\displaystyle Seq(A) = \{ a:\mathbb{Z}^+ \rightarrow A \cup \{0\}  \exists k \in \mathbb{Z}^+ \ni a(i) \in A \forall i < k$, and $\displaystyle a(i) = 0 \forall i \ni i \ge k \}$.
Definition: Call that special k in the above definition $\displaystyle len(a)$ (length of a).
Definition: If $\displaystyle a, b \in Seq(A)$, define $\displaystyle a*b \in Seq(A)$ by $\displaystyle (a*b)(k) = a(k)$ for $\displaystyle k < len(a)$, and $\displaystyle (a*b)(k) = b(klen(a)+1)$ for $\displaystyle k \ge len(a)$.
Definition: If $\displaystyle a \in Seq(A), B \subset Seq(A)$, define $\displaystyle a*B \subset Seq(A)$ by $\displaystyle a*B = \{a*b  b \in B \}$. Similarly for $\displaystyle B*a$.
Define: $\displaystyle a * \emptyset = \emptyset$ for all $\displaystyle a \in Seq(A)$.
Definition: If $\displaystyle k \in A$, define $\displaystyle c_k \in Seq(A)$ by $\displaystyle c_k(1) = k$, and $\displaystyle c_k(i) = 0$ for $\displaystyle i >1$.
Definition: Let $\displaystyle Combination(n, A) = \{ a \in Seq(A)  \Sigma_{i=1}^{\infty} a(i) = n \}$.
All that overhead crap is for a very simple recursive algorithm:
$\displaystyle Combination(n, A) = \cup_{k \in A, k<=n} (c_k * Combination(nk, A))$

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