# Target Sum Subsets - Dp

#### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`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 nn1n2.. n number of elementsA number tar`
Output Format
`true or false as required`
Question Video
Constraints
`1 <= n <= 300 <= n1, n2, .. n elements <= 200 <= tar <= 50`
Sample Input
`54271310`
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

Run

Run
Id Name