# Math Help - Sum Subsets

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

2. ## 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 re-defined by "b starts replacing the 1st occurance of 0 in a"
This is all mumbo-mubo, 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 $A \subset \mathbb{Z}^+$, define $Seq(A) = \{ a:\mathbb{Z}^+ \rightarrow A \cup \{0\} | \exists k \in \mathbb{Z}^+ \ni a(i) \in A \forall i < k$, and $a(i) = 0 \forall i \ni i \ge k \}$.

Definition: Call that special k in the above definition $len(a)$ (length of a).

Definition: If $a, b \in Seq(A)$, define $a*b \in Seq(A)$ by $(a*b)(k) = a(k)$ for $k < len(a)$, and $(a*b)(k) = b(k-len(a)+1)$ for $k \ge len(a)$.

Definition: If $a \in Seq(A), B \subset Seq(A)$, define $a*B \subset Seq(A)$ by $a*B = \{a*b | b \in B \}$. Similarly for $B*a$.

Define: $a * \emptyset = \emptyset$ for all $a \in Seq(A)$.

Definition: If $k \in A$, define $c_k \in Seq(A)$ by $c_k(1) = k$, and $c_k(i) = 0$ for $i >1$.

Definition: Let $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:

$Combination(n, A) = \cup_{k \in A, k<=n} (c_k * Combination(n-k, 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 n-k, and then include k".