Subset sum problem

Given a set of integers, find if there is a subset with a sum equal to S where S is an integer.

This problem is commonly known as a subset sum problem.

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 = 15, 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 the knapsack problem. In the Knapsack problem, we had a limited capacity and we could take anything which does not exceed the limit. However there is a difference, in the knapsack problem, we were allowed to take items less than capacity if the value was greater than all other combinations. In the subset sum problem, we need to discard subsets that have the sum less than S.

What was the basic strategy for solving the 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.

Subset sum problem: Algorithm

Algorithm for find subset with a given sum using recursion is as follows:
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?

If the sum expected of remaining elements in sub-problem is equal to zero at any given point of time, the subset with the given sum 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 the help of some bookkeeping, we can also print all subsets with the given sum.

[expand title=”Subset with given sum recusive implementation” tag=”h3″]

#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);
int K = 10;
int subset[n]
printf("Is there subset with Sum = %d : %s",
K, isSubsetSum(set, n, subset, K) ? "Yes": "No");
return 0;
}

[/expand]

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

Two conditions which are must for application of dynamic programming are present in the above problem. The optimal solution to subproblem actually leads to an optimal solution for the original problem. At the same time, we are solving subproblems, again and again, so overlapping subproblems. 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 = True, and T[i] = 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[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[i] = true;

/* If sum is not 0 and set is empty, no subset is there */
for (i = 1; i <= sum; i++)
subset[i] = 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);
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.

There is another problem based on the subset sum problem called: Partition Equal Subset Sum

class Solution {
public boolean canPartition(int[] nums) {

int sum = 0;

for(int i=0; i<nums.length; i++){
sum+=nums[i];
}

if(sum % 2 == 1) return false;

int rSum = sum/2;

return isSubset(nums, rSum);
}

private boolean isSubset(int [] a, int sum){

boolean [][] dp = new boolean[a.length+1][sum+1];

for(int i=0; i<=a.length; i++){
dp[i] = true;
}

for(int i=1; i<=sum; i++){
dp[i] = false;
}

for(int i=1; i<=a.length; i++){
for(int j=1; j<=sum; j++){
dp[i][j] = dp[i-1][j];

if(j >= a[i-1]){
dp[i][j] = dp[i][j] || dp[i-1][j-a[i-1]];
}
}
}

return dp[a.length][sum];
}
}

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.