Find subset with given sum (Subset sum problem)

Subset sum problem

Given a set of integers, find out all subsets which have sum equal to a given number. Generic case would be given a set of integers and an integers S, find all subsets which have sum equal to S.

Here, we need to find all elements (present in set) whose sum does not exceed S. This condition is similar to what we have in knapsack problem. In Knapsack problem, we had a limited capacity and we could take anything which does not exceed the limit. However there is a difference, in knapsack problem, we were allowed to take items less than capacity if value was greater than all others combinations. Here we need to discard subsets which have sum less than S. So, what was the basic strategy for solving knapsack problem? Yes, take each item and check if it fits in constraint. If it does, we would take that item and reduce the problem to a sub problem looking in N-1 items and reduced capacity of C-v where v was value of item included.
If chosen item does not satisfy the constraint, ignore it and reduce problem to N-1 items and capacity C.
Same principle applies here too.

Find subset with given sum : Algorithm

Algorithm for subset sum problem using recursion. For each integer in set, there are two options:
1. Include current integer in solution.
2. Do not include the integer in solution
Choice we make above,will reduce original problem to sub problem with N-1 elements and either S-v or S as sum expected for those N-1 elements.

When do we stop reducing problems into sub-problems? What would be the base case? If sum expected out of remaining elements in sub-problem is equal to zero at any given time, subset is found. If we have visited all elements of set and yet not achieved expected sum S (In this case, we have not elements while expected sum is still greater than 0), there is no subset.

If sum == 0  return true
If n == 0 && sum != 0 return false

With help of some book keeping, we can also print all the subsets.

Subset sum problem : Implementation

#include<stdlb.h>
#include<stdio.h>

#define true 1
#define false 0
int isSubsetSum(int arr[], int n, int sum,
                int subset[], int count){
  int i;
  if(sum == 0) {
       printf("\n");
       for(i =0; i < count; i++)
           printf("%d  ",  subset[i]);
           return true;
       }
  if(n < 0  && sum != 0)  return false;

  subset[count] =  arr[n];
  return
         isSubsetSum(arr, n-1, sum-arr[n], subset, count + 1)  
         || isSubsetSum(arr, n-1, sum, subset, count );
}

/* Driver program */
int main(){
 
  int set[] = {1,3,5,4,6};
  int n  =  sizeof(set)/sizeof(set[0]);
  int K = 10;
  int subset[n]
  printf("Is there subset with Sum = %d : %s",
          K, isSubsetSum(set, n, subset, K) ? "Yes": "No");
  return 0;
}

Complexity of algorithm to find subset in an array with a given sum is (2N) as in worst case it has to go through all the subsets (of length 1 to N ) of set.

Subset sum problem using Dynamic programming approach

Below code is for finding if there is subset present with given sum. I have to come up with a mechanism to find out which all subsets form that sum.
This code has complexity of O(N * SUM) and uses O(N * SUM) extra space.

#include<stdlib.h>
#include<stdio.h>

int isSubsetSum(int arr[], int n, int sum)
{
  /* The value of subset[i][j] will be true if there is a 
  subset of set[0..j-1] */
  int subset[sum+1][n+1];
  int i,j;
      
  /* If sum ==0, there will be empty set satisfying that condition
  hence row with sum = 0 will have all true values. */
  for (i = 0; i <= n; i++)
    subset[0][i] = true;

  /* If sum is not 0 and set is empty, no subset is there */ 
  for (i = 1; i <= sum; i++)
    subset[i][0] = false;

  for (i = 1; i <= sum; i++)
  {
    for ( j = 1; j <= n; j++)
    {
        /* If there is subset with j-1 elements, copy value */
        subset[i][j] = subset[i][j-1];
        
        /* Now if the latest element can be added */
        if (i >= arr[j-1])
            subset[i][j] = subset[i][j]
                           ||subset[i-arr[j-1]][j-1];
    }
  }
  return subset[sum][n];
}

/* Driver program */
int main(){
 
  int set[] = {1,3,5,4,6};
  int n  =  sizeof(set)/sizeof(set[0]);
  int K = 10;
  printf("Is there subset with Sum = %d : %s",
          K, isSubsetSum(set, n, K) ? "Yes" : "No");
  return 0;
}

Please share if there is something wrong or missing in post. We would love to hear from you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s