title: find a solution to subset sum using dynamic programming
body: <p><strong>What I want to do</strong> </p>
  
  <p>I want to find a subset of an array that sums to a target <code>T</code>. I also want to use to a dynamic programming approach (and a bottom-up solution at that) to do this.</p>
  
  <p><strong>What I currently have</strong></p>
  
  <p>Currently I only found a way to see if amongst all subsets of size <code>N</code>, whether or not there is at least one subset that has the desired sum. See code below.</p>
  
  <pre><code>public boolean solve(int[] numbers, int target) {
  
      //Safeguard against invalid parameters
      if ((target &lt; 0) || (sum(numbers) &lt; target)){
          return false;
      }
  
      boolean [][] table = new boolean [target + 1] [numbers.length + 1]  ;
  
      for (int i = 0; i &lt;= numbers.length; ++i) {
          table[0][i] = true;
      }
  
  
      /* Base cases have been covered. 
       * Now look set subsets [1..n][target] to be true or false.
       * n represents the number of elements from the start that have a subset 
       * that sums to target
       */
      for (int i = 1; i &lt;= target; ++i){
          for (int j = 1; j &lt;= numbers.length; ++j){
              /* Mark index j as one of the numbers in the array
               *  which is part of the solution with the given subtarget */
              table [i][j] = table[i][j-1];
              if (i &gt;= numbers[j-1])
                  table[i][j] = table[i][j] || table[i - numbers[j-1]] [j-1];
          }
      }
  
      return table[target][numbers.length];
  }
  </code></pre>
  
  <p><strong>Where I am stuck</strong></p>
  
  <p>Right now, I know if there <em>is</em> a solution, but I can't think of a way to actually output a solution. </p>
  
  <p>I am not looking for anyone to provide me specific code, but pseudocode is welcome as are hints to how a solution may be saved.</p>