title: Dynamic programming : perfect sum with negative numbers
body: <p>Given an array of integers and a sum, the task is to print all subsets of given array with sum equal to given sum.</p>
  
  <pre><code>Example: 
  Input : arr[] = {1, 2, 3, 4, 5}
          sum = 10
  Output : [4 3 2 1]  
           [5 3 2] 
           [5 4 1]
  
  Input : arr[] = {-1, 2, 3, 4, 5}
          sum = 10
  Output : [5 3 2] 
           [5 4 2 -1]
  </code></pre>
  
  <p>I have done that using dynamic programming in pseudo polynomial time. This is an extension of subset sum problem, which only takes care of deciding whether such a subset exist or not. My solution below works for both positive and negative numbers for the subset sum problem. However, it is not able to print the subsets correctly if the array contains negative numbers.The program is-</p>
  
  <pre><code>import java.util.ArrayList;
  
  // sum problem
  class GFG {
  
      static boolean subset[][];
  
      // Returns true if there is a subset of
      // set[] with sun equal to given sum
      static boolean isSubsetSum(int set[],
                                 int n, int sum) {
          // The value of subset[i][j] will be
          // true if there is a subset of
          // set[0..j-1] with sum equal to i
          subset = new boolean[n + 1][sum + 1];
  
          // Fill the subset table in botton
          // up manner
          for (int i = 0; i &lt;= n; i++) {
              for (int j = 0; j &lt;= sum; j++) {
                  if (j == 0) {
                      subset[i][j] = true;
                  } else if (i &lt;= 0 &amp;&amp; sum &gt;= 1)
                      subset[i][j] = false;
                  else if (set[i - 1] &gt; j)
                      subset[i][j] = subset[i - 1][j];
                  else {
                      if (set[i - 1] &gt;= 0)
                          subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
                      else
                          subset[i][j] = subset[i - 1][j] || subset[i - 1][j + set[i - 1]];
                  }
              }
          }
  
          // uncomment this code to print table
  //        for (int i = 0; i &lt;= sum; i++)
  //        {
  //        for (int j = 0; j &lt;= n; j++)
  //            System.out.println (subset[i][j]);
  //        }
  
          return subset[n][sum];
      }
  
      /* Driver program to test above function */
      public static void main(String args[]) {
          int set[] = {1, 2, 3, 4, 5};
          int sum = 10;
          int n = set.length;
          if (isSubsetSum(set, n, sum) == true)
              System.out.println("Found a subset"
                      + " with given sum");
          else
              System.out.println("No subset with"
                      + " given sum");
          System.out.println("Done");
          ArrayList&lt;Integer&gt; list = new ArrayList&lt;&gt;();
          printSubsets(set, n, sum, list);
          System.out.println("Finished");
      }
  
      static void display(ArrayList&lt;Integer&gt; v) {
          System.out.println(v);
      }
  
      private static void printSubsets(int[] set, int i, int sum, ArrayList&lt;Integer&gt; list) {
          if (i == 0 &amp;&amp; sum != 0 &amp;&amp; subset[0][sum]) {
              list.add(set[i]);
              display(list);
              list.clear();
              return;
          }
  
          // If sum becomes 0
          if (i == 0 &amp;&amp; sum == 0) {
              display(list);
              list.clear();
              return;
          }
  
          // If given sum can be achieved after ignoring
          // current element.
          if (subset[i - 1][sum]) {
              // Create a new vector to store path
              ArrayList&lt;Integer&gt; b = new ArrayList&lt;&gt;();
              b.addAll(list);
              printSubsets(set, i - 1, sum, b);
          }
  
          // If given sum can be achieved after considering
          // current element.
  
          if (sum &gt;= set[i - 1] &amp;&amp; subset[i - 1][sum - set[i - 1]]) {
              list.add(set[i - 1]);
              printSubsets(set, i - 1, sum - set[i - 1], list);
          }
  
      }   
  } 
  </code></pre>
  
  <p>How this code can be modified to work for negative numbers as well?</p>