java - Finding all possible subset sum which is equal to 0 out of set of positive and negative numbers? -

this question has answer here:

• given set of n integers, return subsets of k elements sum 0 3 answers

you have array has set of positive , negative numbers, print subset sum equal 0.

i can think of approach can cam make powersets of givcen array , check if sum 0. not llok optimized solution me.

after reading looks bit similar problem on net , looks can solved dynamic programming below program find if there combination exist make sum 11 example ?

public boolean subsetsum(int input[], int total) {          boolean t[][] = new boolean[input.length + 1][total + 1];         (int = 0; <= input.length; i++) {             t[i][0] = true;         }          (int = 1; <= input.length; i++) {             (int j = 1; j <= total; j++) {                 if (j - input[i - 1] >= 0) {                     t[i][j] = t[i - 1][j] || t[i - 1][j - input[i - 1]];                 } else {                     t[i][j] = t[i-1][j];                 }             }         }         return t[input.length][total];      }     public static void main(string args[]) {     testdynamic ss = new testdynamic();    int arr1[] = {2, 3, 7, 8};     system.out.print(ss.subsetsum(arr1, 11));  } 

but not sure how extend above programe

1) include negative number
2) find combination of elements whick makes sum zero( above program finds whether possible make given sum not find set of numbers makes zero)

here full implementation in javascript. can run node.js.

function target_sum(a, k, x) {     if (k == a.length) return [];     if (a[k] == x) {         return [[a[k]]];     } else {         var s = target_sum(a, k + 1, x);        // not using a[k]         var t = target_sum(a, k + 1, x - a[k]); // using a[k]         (var = 0; < t.length; ++i) {             t[i].unshift(a[k]); // a[k] part of solution             s.push(t[i]);       // merge t[] s[]         }         return s;     } }  var s = target_sum([1,4,5,2,7,8,-3,-5,-6,9,3,-7,-1,5,6], 0, 0); (var = 0; < s.length; ++i)     console.log(s[i].join(",")); 

note exponential algorithm. don't use on large arrays.

erwin rooijakkers pointed right direction. in particular, this post gives algorithm. wrong following – believe algorithm trades speed space. avoids staging arrays call stack, has more recursions achieve that.

edit: algorithm mentioned. not exponential, works positive numbers if right. time complexity proportional target sum, may not ideal depending on input.