2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user99680 Dec 1 '13 at 6:20
  • 1
    $\begingroup$ @user99680 But that is inefficient since you would then need to do $2^{100}$ such sums, whereas the total candidates are only $100^2$. $\endgroup$ – user17762 Dec 1 '13 at 6:23
  • $\begingroup$ @user 17762: but aren't we also considering adding triples, quadruples, etc. of numbers? $\endgroup$ – user99680 Dec 1 '13 at 6:24
  • $\begingroup$ @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. $\endgroup$ – user17762 Dec 1 '13 at 6:26
  • $\begingroup$ @user17762: Ah, I see; you're right. $\endgroup$ – user99680 Dec 1 '13 at 6:27
2
$\begingroup$

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.

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

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
$\endgroup$
  • $\begingroup$ @Templar:thanks,it looks better, i didn't knew how to make it look so,my first answer. $\endgroup$ – charany1 Apr 25 '14 at 16:13
  • $\begingroup$ 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 $\endgroup$ – Templar Apr 25 '14 at 16:43
  • $\begingroup$ @Templar:ok,got it. $\endgroup$ – charany1 Apr 25 '14 at 16:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.