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