Backtracking

Subset Sum

Pinterest LinkedIn Tumblr

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.

Reference

  1. http://mathworld.wolfram.com/SubsetSumProblem.html
  2. https://en.wikipedia.org/wiki/Subset_sum_problem
  3. https://eprint.iacr.org/2013/199.pdf
  4. http://www2.informatik.uni-halle.de/dasi/English/4.5.1.e.html

Write A Comment