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$
2
  • 3
    $\begingroup$ Dynamic programming with running time $O(|L|\cdot sum(L))$ can do help for small ranges of integers in $L$. $\endgroup$ May 11, 2016 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$ May 11, 2016 at 11:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.