Target Sum Subsets  Dp
1. You are given a number n, representing the count of elements.Input Format
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.
A number nOutput Format
n1
n2
.. n number of elements
A number tar
true or false as requiredQuestion Video
1 <= n <= 30Sample Input
0 <= n1, n2, .. n elements <= 20
0 <= tar <= 50
5Sample Output
4
2
7
1
3
10
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 i1) of the arr When ith elements is included then from i1 elements we need the subsets whose sum = (s  value of ith element)
if(curr_ele <= sum)
target_sum(arr, i, sum) = target_sum(arr, i1, sum) OR
target_sum(arr, i1, sum  curr_ele)
Sum = 0 is always formed with the Empty set.
Nonzerosum 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 i1).
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[ i1 ][ j ] ith element is included if and only if j >= arr[ i1 ] then dp[ i ][ j ] = dp[ i1 ][ jarr[i1] ]
Note: ith element in the array have index i1, and the value of the ith element is arr[i1].
dp[ i ][ j ] = dp[ i1 ][ j ]
if(j >= arr[ i1 ]) then
dp[ i ][ j ] = dp[ i1 ][ j ]  dp[ i1 ][ jarr[i1] ]
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 nonzerosum 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[i1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i1][j]  dp[i1][j4]
Filling subsets with 2 elements { 4, 2 }
If sum < 2 then it has only option to exclude i.e, dp[i][j] = dp[i1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i1][j]  dp[i1][j2]
Filling subsets with 3 elements { 4, 2, 7}
If sum < 7 then it has only option to exclude i.e, dp[i][j] = dp[i1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i1][j]  dp[i1][j7]
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[i1][j]
Else it has both option to include and exclude i.e., dp[i][j] = dp[i1][j]  dp[i1][j1]
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 i1 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