Problem Statement:
You are given a non-negtive integers and a sum, you need to check if there is a subset with the sum equal to the given sum.
Example
Input: arr = {1, 2, 3, 4, 5} sum = 9
Output: True
Because there is a subset {4, 5} with the sum = 9
Solution
Before we start with the solution to the problem, we shall understand few points:
1. Below problems are the variations of 0/1 Knapsack problem
Subset sum
Equal Sum partition
Count of subset sum
Min subset sum diff
Target sum
Number of subset given difference
2. All the above problems can be solved by DP
3. To solve a problem in DP, first we need to solve it with the help of recursion. Then from recursion we need to change it to Top Down approach using memoization. Then that can be converted into Bottom UP DP.
4. Below are the few points that we can check to see if any problem is a variation of 0/1 Knapsack problem
a. In knapsack we create a matrix dp[n+1][w+1]. Where n is the number of items and w is the weight.
b. In that matrix first row and first column will be 0, because if there are no items then the weight will also be 0. That would be our base case. Then we fill the matrix with the help of dp formula.
c. In knapsack we have weight array, value array and capacity of knapsack. We need to get the max profit.
d. In the above 6 problems, we will have one array instead of 2, and we will be having a target sum to be satisfied.
e. So now we have few items I1, I2, I3 and need to fill the bag with weight W with max profit.
f. Now for every item we have 2 choices, either choose an item or not to satisfy the max sum given.
g. All the problems like this will fall under Knapsack Problem.
Now we will solve the problem:
1. Recursion relation
So according to the problem we need to check if there are 2 values that will add up to the given sum and we need to return true or false.
In this problem we have an array and a target sum.
Then for every element we have 2 choices, whether to choose that element or we can ignore that element. By making those choices we need to check if they add up to the sum.
As I informed you earlier at every step we can either choose an element or leave an element. According to that we can write the statement as:
Case 1: If we choose an element, then “req_sum = target_sum – value_of_last_element” and total_num_of_elements = total_elements – 1.
Case 2: If we do not choose the last element, then “req_sum = target_sum” and total_num_of_elements = total_elements – 1.
The recurrence relation can be written as:
isSubsetSum(set, n, sum)
= isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1])
Here we have 2 choices either we take that element or to leave that element.
2. Bottom Up Approach using tabulation
To convert into Top Down approach we need to create a 2D array.
For knapsack we created an array of DP[n+1][w+1].
Here also we can create an array of DP[n+1][sum+1].
Also, a sample array will look like below:
From the image above, the first row will be true because, even if we have a number, there is always a empty sub set with the sum = 0.
The first column will be false because, with zero numbers you cannot have any sum.
So below will be our base case:
if (i == 0)
DP[i][j] = F
if (j == 0)
DP[i][j] = T
Now we will get the formula to fill the rest of the array.
That is very simple as shown below:
if (arr[i-1] > j)
DP[i][j] = DP[i-1][j]
else
DP[i][j] = DP[i-1][j] OR DP[i-1][j-A[i-1]]
Solution in C++
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <unordered_set>
#include <list>
using namespace std;
bool subset_sum_recursive(int set[], int n, int sum)
{
if (sum == 0)
return true;
if (n == 0)
return false;
// check if last element is greater than sum,
// then ignore it
if (set[n - 1] > sum)
return subset_sum_recursive(set, n - 1, sum);
return subset_sum_recursive(set, n - 1, sum)
|| subset_sum_recursive(set, n - 1, sum - set[n - 1]);
}
bool subset_sum_tabulation(int set[], int n, int sum)
{
bool subset[n + 1][sum + 1];
for (int i = 0; i <= n; i++)
subset[i][0] = true;
for (int i = 1; i <= sum; i++)
subset[0][i] = false;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
//if the current element value h=is greater than "current sum value",
//then copy the answer for previous case
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j]
|| subset[i - 1][j - set[i - 1]];
}
}
/* // print table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= sum; j++)
printf ("%4d", subset[i][j]);
printf("\n");
}*/
return subset[n][sum];
}
int main()
{
int set[] = { 1, 2, 3, 4, 5 };
int sum = 9;
int n = sizeof(set) / sizeof(set[0]);
if (subset_sum_recursive(set, n, sum) == true)
cout << "Subset with the sum is present using recursive"<<endl;
else
cout << "Subset with the sum is not present using recursive"<<endl;
if (subset_sum_tabulation(set, n, sum) == true)
cout << "Subset with the sum is present using tabulation"<<endl;
else
cout << "Subset with the sum is not present using tabulation"<<endl;
return 0;
}Output:
Subset with the sum is present using recursive
Subset with the sum is present using tabulation