Most of the time, dynamic programming is just a faster way to do things with recursion. You use dynamic programming to optimize any recursive solution that makes use of the same inputs repeatedly. Subproblem results will be stored, so they do not have to be recomputed in the future as needed. This straightforward optimization decreases the time complexity from exponential to polynomial levels.
By the end of this tutorial, you will better understand the recursion and dynamic programming approach to the subset sum problem with all the necessary details and practical implementations.
What Is the Problem Statement for the Subset Sum Problem?
You will be given a set of non-negative integers and a value of variable sum, and you must determine if there is a subset of the given set with a sum equal to a given sum.
Now, look at the recursive solution to solve the subset sum problem.
What Is the Recursion Based Solution to the Subset Sum Problem?
For the recursion based approach, you will look at two scenarios:
- Start with the last element and work your way up to the goal sum by subtracting the value of the 'last' element from the total number of elements.
- 'Final' element will be removed, and the required sum will equal the target sum, with the number of elements equal to the total elements minus 1.
And this is how you solve the subset sum problem using recursion. Now, implement this solution through a simple C++ code.
How Do You Implement the Recursion-Based Solution of the Subset Sum Problem?
You will be provided with a set with elements {10, 7, 8, 9, 1, 5}. You are to find a subset whose sum must be equal to 16, which is set {7, 9}.
Code:
// A c++ program to illustrate recursion based solution
#include <bits/stdc++.h>
using namespace std;
//It will return true if subset of set[]
//has sum equal to given sum; false otherwise
bool is_subset_sum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0)
return false;
// If last element is greater than sum,
// then we will ignore it
if (set[n - 1] > sum)
return is_subset_sum(set, n - 1, sum);
/* otherwise,we will check if the sum can be obtained by any
of the following:
(a) including the last element
(b) excluding the last element */
return is_subset_sum(set, n - 1, sum)
|| is_subset_sum(set, n - 1, sum - set[n - 1]);
}
// Driver code
int main()
{
int set[] = { 10, 7, 8, 9, 1, 5 };
int sum = 16;
int n = sizeof(set) / sizeof(set[0]);
if (is_subset_sum(set, n, sum) == true)
cout <<"Found a subset with given sum";
else
cout <<"No subset with given sum was found";
return 0;
}
You have now explored the recursive approach to the subset sum problem with a code. Now, look at the dynamic programming-based solution to this problem.
What Is the Dynamic Programming Based Solution to the Subset Sum Problem?
You use dynamic programming to solve the problem in pseudo-polynomial time,
- Make a boolean-type 2D array of size (arr.size() + 1) * (target + 1).
- If there is a subset of elements from A[0....i] with sum value = 'j,' the state DP[i][j] is true.
- To avoid duplicating previous cases' answers, you will have to ensure that the current element has a value greater than the "current sum value."
- So, check if any prior states have already encountered the sum='j' OR have previously experienced the value 'j – A[i], which will help you achieve your purpose if it is bigger than the current total value.
And this is how you solve this problem using dynamic programming. Now implement this solution through a simple C++ code.
How Do You Implement the Dynamic Programming Based Solution of the Subset Sum Problem?
You will be given a set with elements as {10, 7, 8, 4, 1, 6}. You have to find a subset whose sum must be equal to 16, which is set {10, 6}.
Code:
// A C++ program to demonstrate Dynamic Programming
//approach to solve this problem
#include <bits/stdc++.h>
using namespace std;
//It will return true if subset of set[]
//has sum equal to given sum; false otherwise
bool is_subset_sum(int set[], int n, int target_sum)
{
//If set[0..j-1] has a subset with
//target_sum equal to i then the
//value of sub_set[i][j] will be true.
bool sub_set[n + 1][target_sum + 1];
// If target_sum is 0, then answer is true
for (int i = 0; i <= n; i++)
sub_set[i][0] = true;
// If target_sum is not 0 and set is empty,
// then answer is false
for (int i = 1; i <= target_sum; i++)
sub_set[0][i] = false;
// we will now fill the subset table in bottom up manner
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target_sum; j++) {
if (j < set[i - 1])
sub_set[i][j] = sub_set[i - 1][j];
if (j >= set[i - 1])
sub_set[i][j] = sub_set[i-1][j]
|| sub_set[i - 1][j - set[i - 1]];
}
}
/* // we can uncomment this code to print table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= target_sum; j++)
printf ("%4d", sub_set[i][j]);
cout <<"\n";
}*/
return sub_set[n][target_sum];
}
int main()
{
int set[] = { 10, 7, 8, 4, 1, 6 };
int target_sum = 16;
int n = sizeof(set) / sizeof(set[0]);
if (is_subset_sum(set, n, target_sum) == true)
cout <<"Found a subset with given sum = "<<target_sum;
else
cout <<"No subset found with given sum = "<<target_sum;
return 0;
}
With this, you have come to an end of this tutorial. You will now look at what could be your next steps to conquer dynamic programming problems.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
Your next stop in mastering dynamic programming problems should be matrix chain multiplication. Given a list of matrices, you must find the most efficient way to multiply a set of matrices together. The issue isn't whether or not to multiply, but rather which multiplications to perform first.
If you're searching for a more in-depth understanding of software development that can help you carve out a successful career in the field, look no further. If that's the case, consider Simplilearn's Postgraduate Program in Full Stack Web Development, which is offered in collaboration with Caltech CTME, the world's largest technology education institution. This Post-Graduate Program will teach you how to master both front-end and back-end Java technologies, beginning with the fundamentals and progressing to the more advanced aspects of Full Stack Web Development. In this web development course, you'll study Angular, Spring Boot, Hibernate, JSPs, and MVC, which will help you get started as a full-stack developer.
If you have any questions or require clarification on this "Subset Sum Problem" tutorial, please leave them in the comments section below. Our expert team will review them and respond as soon as possible.
