# Given a vector of positive integers, count the number of combinations which have a sum that produces a different value

I have a list (vector) of positive integer numbers, including repetitions. For example, $L = [1, 1, 4, 1, 3]$; I want to calculate the number of different sums obtained by using the elements of $L$, according to their multiplicities.

For example, if $L = [10, 30, 100]$, these sums are $$sum = \{0, 10, 30, 40, 100, 110, 130, 140\}$$ because $$sum = \{0,10,30,10+30,100,100+10, 100+30, 100+10+40\}$$

The problem is to determine the cardinality of the $sum$ set.

In the last case, $|sum| = 2^3 = 8$; however, if $L = [1,1,1,1]$, then $$sum = [0,1,2,3,4]$$ and $|sum| = 5$.

Must I check all possible $2^k$ ways of sum the elements of $L$ (where $k$ is the length of $L$) in order to calculate $|sum|$?

• Dynamic programming with running time $O(|L|\cdot sum(L))$ can do help for small ranges of integers in $L$. – Max Alekseyev May 11 '16 at 10:00
• In the second example obviously there is a 4 missing in sum. On the other hand, I am wondering how you get the 5, 6, 7, and 8 as sum of four 1s. – Johannes Trost May 11 '16 at 11:48