Target Sum Subsets - Dp

Prev Next

1. You are given a number n, representing the count of elements.
2. You are given n numbers.
3. You are given a number "tar".
4. You are required to calculate and print true or false, if there is a subset the elements of which add 
     up to "tar" or not.

Input Format

A number n
n1
n2
.. n number of elements
A number tar

Output Format

true or false as required

Question Video

Constraints

1 <= n <= 30
0 <= n1, n2, .. n elements <= 20
0 <= tar <= 50

Sample Input

Sample Output

true

Editorial
Difference between subset and subarray:
Subset: Need not be continuous.
Subarray: Must be continuous.
Ex: { 1, 2, 3 }
Has 2^3 = 8 subsets, and (3*4)/2 = 6 subarrays
Approach:
While forming a subset, each element of the array has 2 choices
1. It will not be included in the subset.
2. It will be included in the subset.
If the current element is not included, then the remaining elements should form the subset with a given sum Current element can be part of a subset if and only if the sum >= current elements value. If the current element is included, then the remaining elements should form the subset with the remaining sum( sum - current elements value ) This can be recursively written as follows Let target sum(arr, i, s) represents, Can sum "s" be formed with subsets of first i elements(Indexed from 0 to i-1) of the arr When ith elements is included then from i-1 elements we need the subsets whose sum = (s - value of ith element)
if(curr_ele <= sum)
target_sum(arr, i, sum) = target_sum(arr, i-1, sum) OR
target_sum(arr, i-1, sum - curr_ele)
Sum = 0 is always formed with the Empty set.
Non-zero-sum with zero Elements can never be formed.
Tabulation Method:
1.Create the dp table to store boolean values with
Rows = n + 1 Columns = sum + 1
2.Meaning: dp[i][j] will represent the subset with sum = j can be formed with the first i elements of the array(indexed from 0 to i-1).
3.Required answer will be in dp[n][sum]
4.Base Condition: Sum = 0 is always formed i.e., dp[ i ][ j ] = true where j = 0 and i from 0 to n.
Non zero sum with zero elements is never possible i.e., dp[ i ][ j ] = false where i = 0 and j != 0
5. Recursive Equation: ith element is excluded then dp[ i ][ j ] = dp[ i-1 ][ j ] ith element is included if and only if j >= arr[ i-1 ] then dp[ i ][ j ] = dp[ i-1 ][ j-arr[i-1] ]
Note: ith element in the array have index i-1, and the value of the ith element is arr[i-1].
dp[ i ][ j ] = dp[ i-1 ][ j ]
if(j >= arr[ i-1 ]) then
dp[ i ][ j ] = dp[ i-1 ][ j ] || dp[ i-1 ][ j-arr[i-1] ]
Example:
n = 4
arr[ 4 ] = { 4, 2, 7, 1 }
sum = 10
dp[6][11] will be created as follows
Subset with sum = 0 is always possible:
Subset with zero elements but non-zero-sum is never possible
Filling subsets with 1 element { 4 }
If sum < 4 then it has only option to exclude i.e, dp[i][j] = dp[i-1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i-1][j] || dp[i-1][j-4]
Filling subsets with 2 elements { 4, 2 }
If sum < 2 then it has only option to exclude i.e, dp[i][j] = dp[i-1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i-1][j] || dp[i-1][j-2]
Filling subsets with 3 elements { 4, 2, 7}
If sum < 7 then it has only option to exclude i.e, dp[i][j] = dp[i-1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i-1][j] || dp[i-1][j-7]
Filling subsets with 4 element { 4, 2, 7, 1}
If sum < 1 then it has only option to exclude i.e, dp[i][j] = dp[i-1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i-1][j] || dp[i-1][j-1]
Final Dp table:
Required and = dp[n][sum] i.e., dp[4][10] = True.
```
bool target_sum(vector
 &arr, int n, int target)
                                {
                                    bool dp[n + 1][target + 1];
                                    //dp[i][j] => Is there a subset with first i elements which can form sum of j;
                                    for (int i = 0; i <= n; i++)
                                    {
                                        for (int j = 0; j <= target; j++)
                                        {
                                            if (i == 0 && j == 0)
                                            {
                                                //sum 0 with no elements is possible
                                                dp[i][j] = true;
                                            }
                                            else if (i == 0)
                                            {
                                                // Non zero sum(as j != 0) with no elements is never possible
                                                dp[i][j] = false;
                                            }
                                            else if (j == 0)
                                            {
                                                //sum zero is always possible
                                                dp[i][j] = true;
                                            }
                                            else
                                            {
                                                dp[i][j] = dp[i - 1][j]; //when excluding the ith number
                                                int val = arr[i - 1];    //ith number will have index i-1
                                                if (j >= val)
                                                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - val];
                                            }
                                        }
                                    }
                                    return dp[n][target]; //return if target can be formed with first n numbers.
                                }
```
java false
Time complexity:
Each cell of the DP table take O(1) time
Total Number of Cell in the dp table = (n+1)*(sum+1) = n*sum + n + sum + 1
Total time = (n*sum + n + sum + 1) * O(1)
= O(n*sum).
Thus,
Time complexity = O(n*sum)
Space Complexity = Size of the DP table = O(n*sum) - Senojiya Jill Patel
Asked in Companies
Related Topics