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

#### Algorithms Dynamic Programming (DP) Subset Sum problem

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

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

#### Kyatham Srikanth

Software Developer at Optum | Summer Research Intern at Central Institute Of Mining & Fuel Research (2017) and OpenGenus (2018) | B. Tech (2019) at Indian Institute of Technology (IIT BHU), Varanasi