Subset Sum Problem Dynamic programming

Problem Statement of Subset Sum Dynamic Programming

Given a set T containing a list of integers and a sum S, does a subset of T exists whose sum is equal to S.

NOTE – Subset of a set is collection where each element of the set exists at most 1 time.

Now let’s us see the implementation for Subset Sum Dynamic Programming.

This problem can be solved using Naive Recursion and also by Dynamic Programming (will see later). Before solving let’s see the sub-problem in this case.

Sub Problem

Suppose we are given a set T of n elements and a sum S. Since we have to find a subset of T whose sum is equal to S.

So let’s proceed in the following manner –

• For ith element in T i.e. T[i], we have two choices whether to include them or exclude them. Therefore the recursive function would be recursion(S-T[i],k) || recursion(S,k) where || is OR and k is number of remaining elements . (Here our recursive function is recursion(int S,int k) )
• Also the base cases are
  • If k == -1 and S != 0, then return false as sum of subset is not equal to S.
  • If S == 0, then return true as a subset exists whose sum is equal to S.

Important Note :- There may exists a case where S is zero but all the elements are positive then answer is true because {} is a subset of every set.

Naive Recursion

In naive implementation we will recursively solve each and every sub problem following the recurrence relation that we defined in the previous section.

Code

Implemented in C++

#include <bits/stdc++.h>
#define ll int64_t
#define MX 1000007
using namespace std;
 
int t[MX];                             // contains the set 
 
bool subset_sum(int s,int k){
  if(s==0)                 //Base case if s==0
    return true;
  if(k==0 && s!=0)                   //Base case if s!=0
    return false;
 
  if(t[k-1] > s)                          // if T[k-1] is greater than s then it is better to skip it 
    return subset_sum(s,k-1);
  else
    return subset_sum(s-t[k-1],k-1) || subset_sum(s,k-1);  // recursive with including and excluding T[k-1]
}
 
int main(){
 
  int n,sum;
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>t[i];
  cin>>sum;
 
  (subset_sum(sum,n))?cout<<"Possible":cout<<"Not Possible";
  return 0;
}

Complexity

This naive approach we are solving 2 sub problems for each sub problem irrespective of the fact that we have solved that sub problem previously. So in the worst case we may end up doing O(n*2ⁿ) operations which is exponential complexity.

Dynamic Programming

The Top-down dynamic programming implementation of this problem is almost similar to the naive solution, all we have to do is to memoize the result of each sub problem solved before returning it and we are done.

The bottom-up dynamic programming implementation can be done by creating a 2d matrix dp of dimension (n+1)x(sum+1) where n is the size of the set.

First we will initialise the the first column of dp i.e. dp[][0] with 1 because for any set, a subset is possible with 0 sum i.e null set. After that we will initialise the first row of dp i.e. dp[0][] with 0 because if sum is not empty and set is empty then answer is false. Then we will use use the recursion discussed in Sub problem section.     

Let’s see an example with Sum = 5 and set = {2,2,2,3,4}

Code

Implemented in C++ with 2d dp table

#include <bits/stdc++.h>
#define ll int64_t
#define MX 1000007
#define MX1 1003
using namespace std;
 
int t[MX],dp[MX1][MX1];
 
bool subset_sum(int sum,int n){
 
  for(int i=0;i<=n;i++)
    dp[i][0]=1;
 
  for(int i=1;i<=sum;i++)
    dp[0][i]=0;
 
  for(int i=1;i<=n;i++){
    for(int j=1;j<=sum;j++){
      if(t[i-1]>j)
        dp[i][j]=dp[i-1][j];
      else
        dp[i][j]=dp[i-1][j]|dp[i-1][j-t[i-1]];
    }
  }
 
  for(int i=0;i<=n;i++){
    for(int j=0;j<=sum;j++)
      cout<<dp[i][j]<<" ";
    cout<<endl;
  }
 
  return dp[n][sum];
}
 
int main(){
 
  int n,sum;
  cin>>n;
  for(int i=0;i<n;i++)
    cin>>t[i];
  cin>>sum;
 
  (subset_sum(sum,n))?cout<<"Possible":cout<<"Not Possible";
  return 0;
}

Implemented in C++ with 1d dp table

#include <bits/stdc++.h>
#define ll int64_t
#define MX 1000007
#define MX1 1003
using namespace std;
 
int arr[MX],dp[MX];
 
bool subset_sum(int n,int sum){
 
  dp[0]=1;
  for(int i=0;i<n;i++){
    if(arr[i]<=sum) for(int j=sum;j>=arr[i];j--){
      dp[j]|=dp[j-arr[i]];
    }
  }
 
  return dp[sum];
 
}
 
int main()
{
  int n,sum;
  cin>>n;
  for(int i=0;i<n;i++) cin>>arr[i];
  cin>>sum;
 
  (subset_sum(n,sum))?cout<<"Possible":cout<<"Not Possible";
  return 0;
}

Complexity

Time complexity in both cases for Subset Sum Dynamic Programming is O(sum * n). On the other hand space complexity in first case is O(sum * n) whereas in second case it is O(sum).

Subset Sum Dynamic Programming Article is Published by Arnab Ghosh.
If you want to be a content writer with Gohired.in, please write at career@gohired.in or at admin@gohired.in.