Subset Sum Problem Using Recursion

The subset sum problem is an important problem in complexity theory and cryptography. The problem is NP-complete.

Let's try to understand the problem:

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Examples:

    1. set = {5, 6, 2}, sum = 8

        Output:  True because there is a subset (6, 2) with sum 8.

    2. set = {5, 6, 2}, sum = 7

        Output:  True because there is a subset (5, 2) with sum 7.

Variation: Now, add one constraint here. All 6's must be chosen in the sum of subsets.

So, after adding this constraint Example (2) will return False.

Solution to Subset Sum Problem & Its Variation:

There are many ways to solve this problem. Some of them are-

1. Recursive Solution
2. Dynamic Programming Solution etc.

Let's do this using Recursive Solution.

Following are the steps to achieve the solution-

1. Create a recursive function to determine if there is a subset of the given set with sum equal to given sum.
2. Find frequency of mandatory value.
3. Adjust the sum as per the mandatory value and its frequency in the set.
4. Set all the occurrences of mandatory value to 0 in the set.
5. Call the recursive function to find any such subset.

Following is implementation-


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

/**
 * @author Abhishek
 *
 * This class is used to handle subset sum problem.
 * 
 * Problem: Given a set of non-negative integers, and a value sum, determine if
 *          there is a subset of the given set with sum equal to given sum.
 * It will also take care of additional constraint to pick all the occurrences
 * of some specific element of set.
 * 
 */

public class SubsetSum {
 private int mandVal;
 
 /**
  * Use this if mandatory value constraint is not to be taken care of
  */
 public SubsetSum () {
  // Nothing to do
 } /*end of constructor*/

 /**
  * @param mandVal
  *   mandatory value- always will be part of sum if found in input array 
  */
 public SubsetSum (int mandVal) {
  this.mandVal = mandVal; 
 } /*end of constructor*/

 /**
  * This function finds a subset of set whose elements add up to sum
  * 
  * @param set
  *    set of elements
  * @param n
  *    size of set
  * @param sum
  *    sum to be achieved
  *    
  * @return
  *   true if any subset is found otherwise false
  * 
  */
 boolean isSubsetSum(int set[], int n, int sum) {
  // Base Cases
  if (sum == 0)
   return true;

  if (n == 0 && sum != 0)
   return false;

  // If last element is greater than sum, then ignore it
  if (set[n-1] > sum)
   return isSubsetSum(set, n-1, sum);

  /* else, check if sum can be obtained by any of the following
   (a) including the last element
   (b) excluding the last element */
  return isSubsetSum(set, n-1, sum-set[n-1]) || isSubsetSum(set, n-1, sum);
 } /*end of isSubsetSum*/

 /**
  * This function finds a subset of set whose elements add up to sum
  * 
  * @param set
  *    set of elements
  * @param sum
  *    sum to be achieved
  *    
  * @return
  *    true if any subset is found otherwise false   
  */
 public boolean isSubsetSumWithMandValue (int[] set, int sum) {
  boolean Trc         = false;
  int     mandValFreq = 0;

  if (set == null) {
   System.err.println("Invalid Input...!!!");
   return(Trc);
  } /*endif*/

  int[]   copySet     = new int[set.length];

  /* find occurrences of mandatory value in the input set and
     set the mandatory values to 0 so that mandatory will not come 
     into sum computation */
  for (int i=0 ; i < set.length; i++) {
   copySet[i] = set[i];
   if(set[i] == mandVal) {
    mandValFreq++;
    copySet[i] = 0;
   } /*endif*/
  } /*endfor*/

  /* subtract the sum of mandatory values from the sum to be achieved. 
     So final sum to be achieved = sum - mandValFreq*mandVal */
  sum -= mandValFreq*mandVal;
  return(isSubsetSum(copySet, set.length, sum));
 } /*end of isSubsetSumWithMandValue*/

 /**
  * @param args
  */
 public static void main(String[] args)   {
    int []      set         = {5,6,2};
    int         mandVal     = 6;

    SubsetSum subsetMand = new SubsetSum(mandVal);
    System.out.println("Set: {5,6,2}, Mandatory value: " + subsetMand.mandVal);

    for (int sum=7; sum <=9 ; sum++) {
     if (subsetMand.isSubsetSumWithMandValue(set, sum)) {
      System.out.println("Found a subset with sum:[" + sum + "]");
     } else {
      System.out.println("No subset found with sum:[" + sum + "]");
     } /*endif*/
    } /*endfor*/
 } /*end of main*/
} /*end of class*/




Output:
Set: {5,6,2}, Mandatory value: 6
No subset found with sum:[7]
Found a subset with sum:[8]
No subset found with sum:[9]