Subset Sum Problem (DP Approach)

Given an array arr[] of integers and the sum value, we have to find whether there is a subset whose value is equal to sum our array arr[].

If it exists, return true else false.

Example :

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

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

Solution:

There can be more than one approach to solve this question, a naive approach would be to solve using an iterative way.

But I’m gonna explain to you using the dynamic programming approach.

This problem is of bounded knapsack type.

So, basically we’ll be solving this problem by using a 2D-matrix of size (n+1)(sum+1).

Figure Source: GeeksforGeeks.

arr[]={3,4,5,2}
target=6

0 1 2 3 4 5 6

0 T F F F F F F

3 T F F T F F F

4 T F F T T F F

5 T F F T T T F

2 T F T T T T T

We made a 2D-matrix of size (n+1) & (sum+1) .

n: size of the array

sum: target value to be find.

Wondering how we formed this matrix?

Let me help you. We first initialised our matrix with row 1 and column 1.

In column 1 we have sum value fixed to 0, while in row 1 we have size fixed to 0.

So for column 1, we can always have a subset whose value exists {}.

And for row 1 starting from column 2 we can’t have any subarray to exist with finite sum value and 0 array size.

Let me code this part for you:

int t[n+1][sum+1];

for(int i=0; i<=n; i++)t[i][0]=true;
for(int j=1; j<=sum; i++) t[0][i]=false;

once we initialized the base condition for our matrix we can now discuss the main code part.

For a particular element in a Knapsack, we can always have two choices, whether to consider it or to reject it.

Let me brief this with the code:

for(int i=1; i<=n; i++){
for(int j=1; j<=sum; j++){

if(j>=arr[i-1]) // if the value is greater than our element
t[i][j]= t[i-1][j] || t[i-1][j-arr[i-1]]; // we can reject it or we can accept.

else
t[i][j]= t[i-1][j]; //we only can reject.
}
}

Now having understood our main condition, we can write the complete code.

Code (C++)

bool isSubsetSum(int arr[], int n, int sum)

{

bool t[n+1][sum+1];

// If sum is 0, then answer is true

for (int i = 0; i <= n; i++)

t[i][0] = true;

// If sum is not 0 and set is empty,

// then answer is false

for (int i = 1; i <= sum; i++)

t[0][i] = false;

// Fill the subset table in botton up manner

for (int i = 1; i <= n; i++)

{

for (int j = 1; j <= sum; j++)

{

if(j<arr[i-1])

t[i][j] = t[i-1][j];

if (j >= arr[i-1])

t[i][j] = t[i-1][j] ||

t[i - 1][j-arr[i-1]];

}

}

return t[n][sum];

}

Time Complexity: O(sum*n), where sum is the ‘target sum’ and ’n’ is the size of array.

Space Complexity: O(sum*n), as the size of 2-D array is sum*n.

Feel free to reach out to me on LinkedIn- https://www.linkedin.com/in/swapnil-shukla-5a1305116/