title: Number of distinct sums from non-empty groupings of (possibly very large) lists
body: <p>Assume that you are given a set of coin types (maximum 20 distinct types) and from each type you have maximum 10^5 instances, such that the total number of all the coins in your list is maximum 10^6. What is the number of distinct sums you can make from non-empty groupings of these coins.</p>
  
  <pre><code>for example, you are given the following lists:
  coins=[10, 50, 100]
  quantity=[1, 2, 1]
  which means you have 1 coin of 10, and 2 coins of 50, and 1 coin of 100. 
  Now the output should be
  possibleSums(coins, quantity) = 9.
  </code></pre>
  
  <p>Here are all the possible sums:</p>
  
  <pre><code>50 = 50;
  10 + 50 = 60;
  50 + 100 = 150;
  10 + 50 + 100 = 160;
  50 + 50 = 100;
  10 + 50 + 50 = 110;
  50 + 50 + 100 = 200;
  10 + 50 + 50 + 100 = 210;
  10 = 10;
  100 = 100;
  10 + 100 = 110.
  </code></pre>
  
  <p>As you can see, there are 9 distinct sums that can be created from non-empty groupings of your coins.
  Notice that the case of sum=110 can be obtained by either 50+50+10 or 100+10 which should be counted only once.</p>
  
  <p>I approached this problem by generating the list of all the possible subsets and checking if the sum of each subset exists in the list of generated sums so far. If no, I would add the sum to the list and proceed. </p>
  
  <p>Here is the code that I've written and works with the small lists:</p>
  
  <pre><code>def possibleSums(coins, quantity):
      if coins is None: return None
      subsets = [[]]
      sums = set()
      next = []
      for coin, quant in zip(coins, quantity):
          for q in range(quant):
              for subs in subsets:
                  s = sum(subs + [coin])
                  if not s in sums:
                      next.append(subs + [coin])
                      sums.add(s)
  
              subsets += next
              next = []
      return len(subsets)-1
  </code></pre>
  
  <p>But this approach does not work with very large input list? For example:</p>
  
  <pre><code>coins = [1, 2]
  quantity = [50000, 2]
  </code></pre>
  
  <p>where it needs to generate 2^50002 subsets and check their corresponding sums, or the following example:</p>
  
  <pre><code>coins = [1, 2, 3]
  quantity = [2, 3, 10000]
  </code></pre>
  
  <p>I think that there should be a solution which doesn't require generating all the subsets, but I have no idea how it should be solved.</p>
  
  <p>Any idea?</p>