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.
 A: 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.
A: 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

