Subset Sum Problem
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with a sum equal to the given sum.
Problem Description: Given problem asks you to check whether it is possible to get a subset whose sum is equal to the given sum as in the question if possible you are asked to print "YES" otherwise print "NO".
Input: The first line contains an integer 'T' denoting the total number of test cases. Each test case constitutes two lines. The first line contains 'N', representing the number of elements in the set and the second line contains the elements of the set.
Output: Print "YES" if there is a subset with a sum equal to the given number and "NO" if there is no subset is present.
Example:
Input:
T = 1
N = 7
[5,6,7,8,9,10,11]
sum = 19
Output:
"YES"
{5,6,8}, {11,8}, {10,9} are possible subset with the sum
of elements of the subset equal to given sum as 19.
Input:
T = 1
N = 3
[5,6,7]
sum = 4
Output:
"NO",
no subset is possible since there is no subset
which has sum equal to given sum=4.
(a) Recursion Approach
In this case, we will consider two possibilities as, we consider the last element and decrease the required sum by that element i.e., required sum=required sum-last element value, array size=array size-1; another case is that we totally neglect the last element's value and decrease the size of the array by one.
required sum=required sum, array size =array size-1;
One more case, if the last element's value is greater than the sum then simply decreases the size of the array by one.
The following steps are used:
Time Complexity for the above approach is exponential.
Code:
Output:
(b) Dynamic Programming Approach
(i) Top-Down Approach:
Here, we will use the memorization method, we will use dp[n][sum] as our dp state, where n is the number of elements and sum is the required sum, we will initialize all the dp[n][sum] as -1 and whenever we get dp[n][sum] as !=-1 we simply return it from the table of dp[n][sum] without recalculating it again and again.
Following steps are used in top-dp:
Time Complexity for the above approach is: O(n*n)
Space Complexity for the above approach is: O(n*n)
Code:
Output:
(ii) Bottom-Up Approach
In this case, we fill the table in a bottom-up manner, we will use dp[n][sum] as our dp state where n is the number of elements in the array and sum is the required sum.
Following are the base cases:
Follow steps are used in bottom-up dp for this problem:
Time Complexity for the above approach is: O(n*n)
space complexity for the above approach is: O(n*n)
Code:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer