Find if there is subset with given sum

Tags: , , , ,

Subset sum problem

Given a set of integers, find if there is a subset which has a sum equal to S where s can be any integer. For example, in set = {2,4,5,3}, if  s= 6, answer should be True as there is a subset {2,4} which sum up to 6. However, for the same set if s = 10, answer would be False as there is no subset which adds up to 10.

Here, we need to find all elements (present in the 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 the value was greater than all others combinations. Here we need to discard subsets which have the sum less than S. So, what was the basic strategy for solving knapsack problem? Yes, take each item and check if it fits in the constraint. If it does, we would take that item and reduce the problem to a subproblem looking in N-1 items and reduced capacity of C-v where v was the value of item included.
If the chosen item does not satisfy the constraint, ignore it and reduce the problem to N-1 items and capacity C. The same principle applies here too.

Find subset with given sum: Algorithm

Algorithm for subset sum problem using recursion. For each integer in the set, there are two options:
1. Include current integer in solution.
2. Do not include the integer in solution
The choice we make above will reduce the original problem to subproblem 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, the subset is found. If we have visited all elements of the 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.

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 );
}

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;
}

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

Subset sum problem using dynamic programming

Two conditions which are must for application of dynamic programming are present in above problem. The optimal solution to subproblem actually leads to optimal solution for the original problem. At the same time, we are solving subproblems again and again. How can we use dynamic programming here then?

Let’s say we to find if j elements in the set which add up to sum i. What if there are no elements in the set, that means j = 0. In this case, no matter what, no sum except 0 is possible. If we store it in a table, T[0][0] = True, and T[i][0] = False for all i > 0 and i< S.

What if we have to find S = 0 for given j elements? In that case, it is always possible to find a set with zero elements (empty subset) which adds up to zero. Therefore, T[0][j] = True for all j >=0 and j <= n.

When would T[i][j] be True otherwise? It can be true in two conditions:

  1. If there is a subset with j-1 elements which already adds up to sum i.
  2. If there is a subset with j-1 elements which add up to i-a[j]. This means adding a[j] to that subset will give us a subset of j elements with sum i.
T[i][j] = T[i-a[j]][j-1] || T[i][j-1]

Make sure that i – a[j] >= 0. This recurrence relation will fill up the table and value T[n][S] will tell us if there is a subset with sum S in the set of n integers.

#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;
}

Dynamic programming implementation of subset problem has the time complexity of O(nS) and uses O(nS) extra space.

Please share if there is something wrong or missing in the post. We would love to hear from you. If you are preparing for an interview and need preparation material, please signup to the website.