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. |