Subset Sum Problem using Dynamic Programming 【O(N*sum) time complexity】

Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

Reading time: 30 minutes | Coding time: 10 minutes

In this article, we will solve Subset Sum problem using a dynamic programming approach which will take O(N * sum) time complexity which is significantly faster than the other approaches which take exponential time.

Subset sum problem is that given a subset A of n positive integers and a value sum is given, find whether or not there exists any subset of the given set, the sum of whose elements is equal to the given value of sum.


Given the following set of positive numbers:

{ 2, 9, 10, 1, 99, 3}

We need to find if there is a subset for a given sum say 4:

{ 1, 3 }

For another value say 5, there is another subset:

{ 2, 3}

Similarly, for 6, we have {2, 1, 3} as the subset.

For 7, there is no subset where the sum of elements equal to 7.

This problem can be solved using following algorithms:

  1. Recursive method
  2. Backtracking
  3. Dynamic Programing

In this article, we will solve this using Dynamic Programming.

Dynamic Programming

We create a boolean subset[][] and fill it in bottom up manner.

subset[i][j] denotes if there is a subset of sum j with element at index i-1 as the last element

subset[i][j] = true if there is a subset with:

* the i-th element as the last element
* sum equal to j

Base cases include:

j=0 then subset[i][0] will be true as the sum for empty set is 0

If i=0, then subset[0][j] will be false, as with no elements, we can get no sum.

subset[i][0] = true as sum of {} = 0

subset[0][j] = false as with no elements we can get no sum

If element at index i (E1) is greater than j, then subset[i][j] = false as we cannot get a subset of positive numbers with E1 as a member.

If we include element at index i (E1), we get

subset[i][j] = subset[i-1][j-E1];

where E1 = array[i-1]

As if element E1 is included, then we need to find a subset with the first i-1 elements such that the sum is j - E1.

At this point, we should have the value of subset[i-1][j-E1] and hence, we compute it instantly.

Dynamic Programming computes [i][j], for each 1 <= i <= n and 1 <= j <= sum, which is true if subset with sum j can be found using items up to first i items.

It uses value of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.


1.We create a boolean subset[][] and fill it in bottom up manner.
2.The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false.
3.Finally, we return subset[n][sum]


Dynamic Programming

  • Worst case time complexity: Θ(n*sum)
  • Space complexity: Θ(sum)


Following is the implementation of the Dynamic Programming approach in C++:

/* Part of Cosmos by OpenGenus Foundation */
using namespace std;
*Find whether or not there exists any subset 
*  of array  that sum up to targetSum
class Subset_Sum
    bool subsetsum_DP(int a[],int n, int sum)
        //boolean matrix to store results
        bool dp[n+1][sum+1];

        //dp[i][j]=whethere there is a subset of sum j in subarray   //a[0....i-1]
        int i,j;
        //for sum=0, there is always a subset possible ie., the empty set
        //if there are no elements in the array, no subset is possible //for a non-zero sum
        //i represents the no. of elements of array considered
            //j represents the sum of subset being searched for
                //if using i-1 elements, there is a subset of desired sum
                //no need to search further
                //the result is true 
                //otherwise, we will inspect
                    //if value of current element is greater than the //required sum
                    //this element cannot be considered
                    //check that after including this element, Is there //any subset present for the remaining sum ie., j-a[i-1]
        return dp[n][sum];
int main()
    int i, n, sum;
    Subset_Sum S;
    cout << "Enter the number of elements in the set" << endl;
    cin >> n;
    int a[n];
    cout << "Enter the values" << endl;
    cout << "Enter the value of sum" << endl;
    cin >> sum;
    bool f = false;
    S.subsetsum_DP(a, n, sum);
    if (f)
       cout << "subset with the given sum found" << endl;
       cout << "no required subset found" << endl;   
    return 0;

This performs better than the recursive and backtracking approaches.