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

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.

Example:

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.

Steps:

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]

Complexity

Dynamic Programming

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

Implementation

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

/* Part of Cosmos by OpenGenus Foundation */
#include<iostream>
using namespace std;
/*
*Find whether or not there exists any subset 
*  of array  that sum up to targetSum
*/
class Subset_Sum
{
    public:
    // DYNAMIC PROGRAMMING
    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;
        //initialization
        //for sum=0, there is always a subset possible ie., the empty set
        for(i=0;i<=n;i++)
            dp[i][0]=true;
        //if there are no elements in the array, no subset is possible //for a non-zero sum
        for(j=1;j<=sum;j++)
            dp[0][j]=false;
        //i represents the no. of elements of array considered
        for(i=1;i<=n;i++)
        {
            //j represents the sum of subset being searched for
            for(j=1;j<=sum;j++)
            {
                //if using i-1 elements, there is a subset of desired sum
                //no need to search further
                //the result is true 
                if(dp[i-1][j]==true)
                    dp[i][j]=true;
                //otherwise, we will inspect
                else
                {
                    //if value of current element is greater than the //required sum
                    //this element cannot be considered
                    if(a[i-1]>j)
                        dp[i][j]=false;
                    //check that after including this element, Is there //any subset present for the remaining sum ie., j-a[i-1]
                    else
                        dp[i][j]=dp[i-1][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;
    for(i=0;i<n;i++)
      cin>>a[i];
    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;
    else
       cout << "no required subset found" << endl;   
    return 0;
}

This performs better than the recursive and backtracking approaches.