title: Dynamic programming idiom for combinations
body: <p>Consider the problem in which you have a value of <code>N</code> and you need to calculate how many ways you can sum up to <code>N</code> dollars using <code>[1,2,5,10,20,50,100]</code> Dollar bills.</p>
  
  <p>Consider the classic DP solution:</p>
  
  <pre><code>C = [1,2,5,10,20,50,100]
  
  def comb(p):
      if p==0:
          return 1
      c = 0
      for x in C:
          if x &lt;= p:
              c += comb(p-x)
      return c 
  </code></pre>
  
  <p>It does not take into effect the order of the summed parts. For example, <code>comb(4)</code> will yield 5 results: <code>[1,1,1,1],[2,1,1],[1,2,1],[1,1,2],[2,2]</code> whereas there are actually 3 results (<code>[2,1,1],[1,2,1],[1,1,2]</code> are all the same).</p>
  
  <p>What is the DP idiom for calculating this problem? (<em>non-elegant</em> solutions such as generating all possible solutions and removing duplicates are not welcome)</p>