Find the non-empty subset whose sum is zero from given set of the integers. For example, given the set {-7, -3, -2, 5, 8}, the answer is yes because the subset {-3, -2, 5} sums to zero.

This problem is an example of NP-complete. Write a program to give the total of values equal to sum S.

## source Code

package com.dsacode.Algorithm.backtracking; public class SubsetSum { public static boolean subSetSumRecur(int [] mySet, int n, int goal){ if (goal ==0){ return true;} if ((goal < 0)|( n >= mySet.length)) return false; if (subSetSumRecur(mySet,n+1,goal - mySet[n])){ System.out.print(mySet[n]+" "); return true;} if (subSetSumRecur(mySet,n+1,goal)) return true; return false; } public static void main(String[] args) { int [] mySet ={2,5,8,9,12,21,33}; int goal =0; for (goal = 0; goal < 10; goal++){ System.out.println("The Goal is : "+goal); System.out.println(goal +"="+subSetSumRecur(mySet, 0, goal)); } } }

## Output

The Goal is : 0 0=true The Goal is : 1 1=false The Goal is : 2 2 2=true The Goal is : 3 3=false The Goal is : 4 4=false The Goal is : 5 5 5=true The Goal is : 6 6=false The Goal is : 7 5 2 7=true The Goal is : 8 8 8=true The Goal is : 9 9 9=true

## Algorithm Explanation

If the subset is satisfying the constraint, print the subset. | |

Exclude the current element and consider next element. | |

Generate the nodes of present level along the breadth of the tree and recur for next levels. |