3
$\begingroup$

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|$?

$\endgroup$
  • 3
    $\begingroup$ Dynamic programming with running time $O(|L|\cdot sum(L))$ can do help for small ranges of integers in $L$. $\endgroup$ – Max Alekseyev May 11 '16 at 10:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Johannes Trost May 11 '16 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.