title: Subset Sum - 2D Dynamic Programming
body: <p>I'm trying to find <strong>ALL</strong> the subsets of a set of n numbers that has a sum of m. For example if I had the set <code>(10,20,30,40,40,50,80)</code> and <code>m = 90</code> the subsets are <code>(10,80)</code>, <code>(20,30,40)</code> and <code>(40,50)</code>. I have code that will find small cases like this using something like...</p>
  
  <pre><code>M[i, j] = max(M[i − 1, j], M[i − 1, j − A[i])
  </code></pre>
  
  <p>then backtracking using...</p>
  
  <pre><code>if (M[n][m]!=0)
  {
      for ( i = n; i &gt;= 1; i --)
          if (M[i - 1][j]!=M[i][j])
          {
              printf ("Use item %d = %d\n", i, A[i]);
              j -= A[i];
          }
  }
  </code></pre>
  
  <p>but when I try larger test cases it will not return all the subsets. Any help would be very appreciated.</p>