Sum of Subsets 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.

Here backtracking approach is used for trying to select a valid subset when an item is not valid, we will backtrack to get the previous subset and add another element to get the solution.

Example:

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True  
There is a subset (4, 5) with sum 9.

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.

Method 1: Recursion.

Approach: For the recursive approach we will consider two cases.

1. Consider the last element and now the required sum = target sum – value of ‘last’ element and number of elements = total elements – 1
2. Leave the ‘last’ element and now the required sum = target sum and number of elements = total elements – 1

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) 
= isSubsetSum(set, n-1, sum) || 
  isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0 

Let’s take a look at the simulation of above approach-:

set[]={3, 4, 5, 2}
sum=9
(x, y)= 'x' is the left number of elements,
'y' is the required sum
  
              (4, 9)
             {True}
           /        \  
        (3, 6)       (3, 9)
               
        /    \        /   \ 
     (2, 2)  (2, 6)   (2, 5)  (2, 9)
     {True}  
     /   \ 
  (1, -3) (1, 2)  
{False}  {True} 
         /    \
       (0, 0)  (0, 2)
       {True} {False}    

Implementation:

// A recursive solution for subset sum problem 
#include <stdio.h> 
  
// Returns true if there is a subset 
// of set[] with sum equal to given sum 
bool isSubsetSum(int set[], int n, int sum) 
{ 
    // Base Cases 
    if (sum == 0) 
        return true; 
    if (n == 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) 
           || isSubsetSum(set, n - 1, sum - set[n - 1]); 
} 
  
// Driver program to test above function 
int main() 
{ 
    int set[] = { 3, 34, 4, 12, 5, 2 }; 
    int sum = 9; 
    int n = sizeof(set) / sizeof(set[0]); 
    if (isSubsetSum(set, n, sum) == true) 
        printf("Found a subset with given sum"); 
    else
        printf("No subset with given sum"); 
    return 0; 
}

Output:

Found a subset with given sum

Example:

Input and Output

Input:
This algorithm takes a set of numbers, and a sum value.
The Set: {10, 7, 5, 18, 12, 20, 15}
The sum Value: 35
Output:
All possible subsets of the given set, where sum of each element for every subsets is same as the given sum value.
{10,  7,  18}
{10,  5,  20}
{5,  18,  12}
{20,  15}

Algorithm

subsetSum(set, subset, n, subSize, total, node, sum)

Input − The given set and subset, size of set and subset, a total of the subset, number of elements in the subset and the given sum.

Output − All possible subsets whose sum is the same as the given sum.

Begin
   if total = sum, then
      display the subset
      //go for finding next subset
      subsetSum(set, subset, , subSize-1, total-set[node], node+1, sum)
      return
   else
      for all element i in the set, do
         subset[subSize] := set[i]
         subSetSum(set, subset, n, subSize+1, total+set[i], i+1, sum)
      done
End

Implementation:

#include <iostream>
using namespace std;

void displaySubset(int subSet[], int size) {
   for(int i = 0; i < size; i++) {
      cout << subSet[i] << "  ";
   }
   cout << endl;
}

void subsetSum(int set[], int subSet[], int n, int subSize, int total, int nodeCount ,int sum) {
   if( total == sum) {
      displaySubset(subSet, subSize);     //print the subset
      subsetSum(set,subSet,n,subSize-1,total-set[nodeCount],nodeCount+1,sum);     //for other subsets
      return;
   }else {
      for( int i = nodeCount; i < n; i++ ) {     //find node along breadth
         subSet[subSize] = set[i];
         subsetSum(set,subSet,n,subSize+1,total+set[i],i+1,sum);     //do for next node in depth
      }
   }
}

void findSubset(int set[], int size, int sum) {
   int *subSet = new int[size];     //create subset array to pass parameter of subsetSum
   subsetSum(set, subSet, size, 0, 0, 0, sum);
   delete[] subSet;
}

int main() {
   int weights[] = {10, 7, 5, 18, 12, 20, 15};
   int size = 7;
   findSubset(weights, size, 35);
}

Output:

10   7  18
10   5  20
5   18  12
20  15