Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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])

 
Subset Sum Problem

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.
Subset Sum Problem - Track Solution

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

    http://www.edufyme.com/code?id=45c48cce2e2d7fbdea1afc51c7c6ad26

    • 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.