# Dynamic Programming — Subset Sum Problem

Objec­tive: Given a set of pos­i­tive inte­gers, and a value sum S, find out if there exist a sub­set in array whose sum is equal to given sum S.

Exam­ple:

```int[] A = { 3, 2, 7, 1}, S = 6

Output: True, subset is (3, 2, 1}
```

We will first dis­cuss the recur­sive approach and then we will improve it using Dynamic Pro­gram­ming.

Recur­sive Approach:

For every ele­ment in the array has two options, either we will include that ele­ment in sub­set or we don’t include it.

• So if we take exam­ple as int[] A = { 3, 2, 7, 1}, S = 6
• If we con­sider another int array with the same size as A.
• If we include the ele­ment in sub­set we will put 1 in that par­tic­u­lar index else put 0.
• So we need to make every pos­si­ble sub­sets and check if any of the sub­set makes the sum as S.
• If we think care­fully this prob­lem is quite sim­i­lar to ” Gen­er­ate All Strings of n bits
• See the code for bet­ter explanation.

Time Com­plex­ity: O(2n).

Approach: Dynamic Pro­gram­ming (Bottom-Up)

Base Cases:

• If no ele­ments in the set then we can’t make any sub­set except for 0.
• If sum needed is 0 then by return­ing the empty sub­set we can make the sub­set with sum 0.

Given — Set = arrA[], Size = n, sum = S

• Now for every ele­ment in he set we have 2 options, either we include it or exclude it.
• for any ith element–
• If include it => S = S-arrA[i], n=n-1
• If exclude it => S, n=n-1.

Recur­sive Equation:

```Base Cases:
SubsetSum(arrA, n, S)= false, if sum > 0 and n == 0
SubsetSum(arrA, n, S)= true, if sum == 0 (return empty set)

Rest Cases
SubsetSum(arrA, n, S) = SubsetSum(arrA, n-1, S)|| SubsetSum(arrA, n-1, S-arrA[n-1])

```

Sub­set Sum Problem

How to track the elements.

• Start from the bottom-right cor­ner and back­track and check from the True is coming.
• If value in the cell above if false that means cur­rent cell has become true after includ­ing the cur­rent ele­ment. So include the cur­rent ele­ment and check for the sum = sum — cur­rent element.

Sub­set Sum Prob­lem — Track Solution

Com­plete Code:

```Output: From DP: true
```

#### You may also like...

• Ankit

my solu­tion, prints all sub­sets with the required sum

• Svein Asleik

Doesn’t that algo­rithm have a ter­ri­ble worst case scenario?

• Ankit

The prob­lem state­ments are dif­fer­ent. Print sub­set with required sum vs print *all* sub­sets with required sum. If you have a solu­tion in mind which mod­i­fies the solu­tion given on the page to print all sub­sets with lower time/space com­plex­ity; I would love to discuss.

• Svein Asleik

Well, the prob­lem was, check if there exists a sub­set. And the space com­plex­ity of the one given here could be reduced fur­ther by just keep­ing it in into one long long array with the size of the sum you want to add up to (O(S)). Gotta save it as num­bers then, and not boolean.

• Pravinth

In the recur­sive solu­tion
solution[index] = 0;// do not select the ele­ment
currSum -= A[index]; //«why this minus?.

• cyn­i­cal

Thank you so much for this solution.

• TechUser2011

I’m try­ing to print this page, but the side­bar on the right is block­ing too much of the page, includ­ing half of the code blocks. Can you please fix this prob­lem? Maybe you can pro­vide a way to print where the right side­bar is removed? Thank you.