# Number of possible sum?

Given a list of integers $a_1,a_2,\dotsc,a_n$, where $0\le a_i\le 100$ for every $i$, where $n\le 100$, find all the distinct possible sums that can be obtained by taking any number of elements from the list and adding them.

Example: for $1,2,3$, the answer is $0,1,2,3,4,5,6$.

My approach was a brute force in which called a recurcive method for an index $i$ and inside that since there are two possibilities (to add a number or to leave it) I once added and again called the recursion and called the recursion again without adding it. This approach is time consuming; can anyone please suggest a faster method because total possible sum is only $10001$ ($0+100\cdot 100$). Thanks.

• If all numbers are different, I would say you have: i)The "empty sum", ii)The "1-sums" $a_1,a_2,..,a_{100}$ , then iii)The "2-sums" $a_i+a_j$ , etc. – user99680 Dec 1 '13 at 6:20
• @user99680 But that is inefficient since you would then need to do $2^{100}$ such sums, whereas the total candidates are only $100^2$. – user17762 Dec 1 '13 at 6:23
• @user 17762: but aren't we also considering adding triples, quadruples, etc. of numbers? – user99680 Dec 1 '13 at 6:24
• @user99680 Yes, we are. But if $1\leq a_1, a_2,\ldots,a_m \leq n$, then the number of possible sums without $a_i$'s repeating is bounded by $mn$, whereas if we look at number of $r$ sums, we would have $\dbinom{m}r$ of them and letting $r$ from $0$ to $m$ would give us a total of $2^m$ sums to look at. – user17762 Dec 1 '13 at 6:26
• @user17762: Ah, I see; you're right. – user99680 Dec 1 '13 at 6:27

## 2 Answers

I would start with an array of length $10001$, filled with zeros to indicate you have not yet found a way to make that total. Set $array[0]$ to $1$ to indicate you can sum to zero with the empty subset Then for each element, loop through the array. Add the element to the indices that are already $1$ and set those indices to $1$. For example, if $a_i=3$ and $array[6]=1$, set $array[9]$ to $1$. This requires $10000n$ loops.

• +1. A minor obvious comment. For a given element $a_i$, first set $array[a_i]=1$ and then proceed. – user17762 Dec 1 '13 at 6:36
• @Ross Millikan nice :) thanks – Ashesh Vidyut Dec 1 '13 at 9:59

Here is my take on this:

hash[0]=true          //sum=0 can be obtained by any empty subset

Now,let SUM=sum of all numbers in array

//Iterate through the entire array

for(i=0 to n-1)
//When i-th element is included in sum,minimum (sum)=a[i],maximum(sum)=SUM
for(j=sum;j>=a[i];j--)
//Now,if sum=j-a[i],is a possible sum value then j would also be a possible value,just add a[i]
if(hash[j-a[i]]==true)
hash[j]=true

//Count number of all possible sum using hash

for(i=0;i<=SUM;i++)      //remember,we just need to go upto SUM
{
if(hash[i]==true)
count++;
}

print count

• @Templar:thanks,it looks better, i didn't knew how to make it look so,my first answer. – charany1 Apr 25 '14 at 16:13
• no problem, just select a text which you want to output as code or something similar and click { } icon called preformatted text or press Ctrl + k – Templar Apr 25 '14 at 16:43
• @Templar:ok,got it. – charany1 Apr 25 '14 at 16:47