Dynamic Programming – Subset Sum Problem

by

Objective: Given a set of positive integers, and a value sum S, find out if there exist a subset in array whose sum is equal to given sum S.

Example:

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

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

We will first discuss the recursive approach and then we will improve it using Dynamic Programming.

Recursive Approach:

For every element in the array has two options, either we will include that element in subset or we don’t include it.

  • So if we take example as int[] A = { 3, 2, 7, 1}, S = 6
  • If we consider another int array with the same size as A.
  • If we include the element in subset we will put 1 in that particular index else put 0.
  • So we need to make every possible subsets and check if any of the subset makes the sum as S.
  • If we think carefully this problem is quite similar to “ Generate All Strings of n bits“
  • See the code for better explanation.

Complete Code:

public class SubSetSumRecursion {
public static void find(int[] A, int currSum, int index, int sum,
int[] solution) {
if (currSum == sum) {
System.out.println("\nSum found");
for (int i = 0; i < solution.length; i++) {
if (solution[i] == 1) {
System.out.print(" " + A[i]);
}
}
} else if (index == A.length) {
return;
} else {
solution[index] = 1;// select the element
currSum += A[index];
find(A, currSum, index + 1, sum, solution);
currSum -= A[index];
solution[index] = 0;// do not select the element
find(A, currSum, index + 1, sum, solution);
}
return;
}
public static void main(String[] args) {
int[] A = { 3, 2, 7, 1};
int[] solution = new int[A.length];
find(A, 0, 0, 6, solution);
}
}

view raw
SubSetSumRecursion.java
hosted with ❤ by GitHub


Time Complexity: O(2n).

Approach: Dynamic Programming (Bottom-Up)

Base Cases:

  • If no elements in the set then we can’t make any subset except for 0.
  • If sum needed is 0 then by returning the empty subset we can make the subset with sum 0.

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

  • Now for every element 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.
Recursive 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

How to track the elements.

  • Start from the bottom-right corner and backtrack and check from the True is coming.
  • If value in the cell above if false that means current cell has become true after including the current element. So include the current element and check for the sum = sum – current element.

Subset Sum Problem - Track Solution

Complete Code:

public class SubSetSum {
public static boolean subSetDP(int[] A, int sum) {
boolean[][] solution = new boolean[A.length + 1][sum + 1];
// if sum is not zero and subset is 0, we can't make it
for(int i=1;i<=sum;i++){
solution[0][i]=false;
}
// if sum is 0 the we can make the empty subset to make sum 0
for(int i=0;i<=A.length;i++){
solution[i][0]=true;
}
//
for(int i=1;i<=A.length;i++){
for(int j=1;j<=sum;j++){
//first copy the data from the top
solution[i][j] = solution[i–1][j];
//If solution[i][j]==false check if can be made
if(solution[i][j]==false && j>=A[i–1])
solution[i][j] = solution[i][j] || solution[i–1][j–A[i–1]];
}
}
return solution[A.length][sum];
}
public static void main(String[] args) {
int[] A = { 3, 2, 7, 1};
System.out.println("\nFrom DP: " + subSetDP(A, 6) );
}
}

view raw
SubSetSum.java
hosted with ❤ by GitHub 

Output: From DP: true

Related Posts: