Subset Sum Problem (DP-08)

You are given a set of positive integers and an integer S, you need to find out whether there exists a non-empty subset with sum S.

Sample Input: { 3, 34, 4, 12, 5, 2 }, S = 9
Expected Output: True
Explanation: Subset { 4, 5 } has sum 9. There might be other possible answers as well.

Algorithm:

The problem is a special case of 0-1 knapsack problem.

  1. This problem can also be solved using dynamic programming similar to 0-1 knapsack problem.
  2. We create a 2D array of size (n+1, S+1).
  3. We initialize row 0 to false because using 0 elements, we can only create sum=0. Hence, we initialize DP [0][i] = false where 1<=i<=sum.
  4. We initialize column 0 to true because sum=0 can always be created using any number of elements if we exclude all the elements.
  5. For any given sum and any given number of elements in the array, there are two possibilities.
    Either we include current item in the subset and recur for remaining items with remaining sum.
    Or we exclude the current item and recur for remaining elements.
  6. The following solution is bottom up approach of dynamic programming.
/* Author => Raunak Jain */
#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> nums, int sum){
	int n = nums.size();
	vector<vector<bool>> dp(n+1, vector<bool>(sum+1));
	for(int i=1; i<=sum; i++){
		dp[0][i]=false;
	}
	for(int i=0; i<=n; i++){
		dp[i][0]=true;
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=sum; j++){
			if(j<nums[i-1]){
				dp[i][j]=dp[i-1][j];
			}else{
				dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
			}
		}
	}
	return dp[n][sum];
}

int main(){
	vector<int> nums = { 3, 34, 4, 12, 5, 2 };
	int sum = 9;
	cout<<helper(nums, sum);
	return 0;
}

Also, check out another popular interview question 0-1 knapsack.

2 comments

Leave a Reply

Your email address will not be published.