Dynamic Programming – Subset Sum Problem

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.


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) {
} 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);
public static void main(String[] args) {
int[] A = { 3, 2, 7, 1};
int[] solution = new int[A.length];
find(A, 0, 0, 6, solution);

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++){
// if sum is 0 the we can make the empty subset to make sum 0
for(int i=0;i<=A.length;i++){
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[i1][j];
//If solution[i][j]==false check if can be made
if(solution[i][j]==false && j>=A[i1])
solution[i][j] = solution[i][j] || solution[i1][jA[i1]];
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


hosted with ❤ by GitHub

Output: From DP: true

9 thoughts on “Dynamic Programming – Subset Sum Problem”

      • The problem statements are different. Print subset with required sum vs print *all* subsets with required sum. If you have a solution in mind which modifies the solution given on the page to print all subsets with lower time/space complexity; I would love to discuss.

        • Well, the problem was, check if there exists a subset. And the space complexity of the one given here could be reduced further by just keeping 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 numbers then, and not boolean.

  1. I’m trying to print this page, but the sidebar on the right is blocking too much of the page, including half of the code blocks. Can you please fix this problem? Maybe you can provide a way to print where the right sidebar is removed? Thank you.

  2. /*Recursive method*/

    using namespace std;

    void subsetSum(int weights[],int target,int sum,vector v,int i,int n){

    for(int i=0;i<v.size();i++){
    cout<<v[i]<<" ";
    cout<=n || sum>target){




    int main(){

    int weights[] ={ 7,8,9,11,20};
    int target =20;
    vector v;
    return 0;


Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.