Subset Sum Problem using DP in C++

In this CPP tutorial, we are going to discuss the subset sum problem its implementation using Dynamic Programming in CPP. We will also discuss Dynamic programming.

Problem Statement: Subset Sum Problem using DP in CPP

We are provided with an array suppose a[] having n elements of non-negative integers and a given sum suppose ‘s’. We have to check whether it is possible to get a subset from the given array whose sum is equal to ‘s’.

What is Dynamic Programming?

If we talk about dynamic programming in simple words it is ‘ just remember the answers of a situation in a problem for further answer the next situations’, such that we do not have to calculate the answer for a situation again and again if it already being answered. We store the answers and use it if that answer is needed further anywhere in the problem if needed instead of calculating it again and again.

Tabulation Method in Dynamic Programming

In the Tabulation method, we fill dp in a bottom-up manner. So, in a bottom-up manner, we store the answer for a base case and start filling answer till size of dp taken which is from the base state to destination state.

Algorithm: Subset Sum Problem in C++

  • Input array ‘a[]’, size of array ‘n’ and sum’s’.
  • Now, take a 2-D dp[][] array to implement dp.
  • Now, start filling dp in a bottom-up manner.
  • Base cases of dp are if sum=0 , then for all value of n dp[n][0]=true and if n=0 and sum!=0 the dp[0][sum]=false always.
  • Now, start filling rest dp table by the following approach
for(i=1 to n)

for(j=1 to sum)

if( j<a[i])

 

In this case, the current element of array cannot add up to give sum equals to j. So, it is only possible if previous elements of subset for the same value of j can add up to give j.

 

So, when (j<a[i])

then dp[i][j]=dp[i-1][j]

 

otherwise, there are two cases when j>=a[i]

Learn also,

one case is current value adds up to give sum j or previous values adds up to give j. So, we can either include the current element or exclude it.

 

So, when ( j>=a[i] )

then dp[i][j]=d[i-1][j] || dp[i-1][j-a[i]]

  • If dp[n][sum]==true then it means that we can get sum by a subset formed from given array.

 

CPP Code implementation of subset sum problem

#include<bits/stdc++.h>

  using namespace std;


  void solve(int a[], int n, int sum)
{
    int i,j;
    
     int dp[n+1][sum+1];
    
    for(i=0;i<=n;i++)
      dp[i][0]=1;
      
      for(j=0;j<=n;j++)
        dp[0][j]=0;
        
          for(i=1;i<=n;i++)
       
        {
              for(j=1;j<=sum;j++)
            
            {
              if(j<a[i])  
               dp[i][j]=dp[i-1][j];
               
               else
                 dp[i][j]=dp[i-1][j] || dp[i-1][j-a[i]];
            }
        }
        
        if(dp[n][sum]==1)
          cout<<"Possible"<<endl;
          
         else
           cout<<"Not Possible"<<endl;
}

 int main()
 {
     int n;
      cin>>n;
      
      int a[n];
      
        for(long i=0;i<n;i++)
      {
         cin>>a[i]; 
      }
      
        int sum;
        cin>>sum;
        
          solve(a,n,sum);
 }

INPUT

5
10 1 2 8 1
9

OUTPUT

Possible

In the above example, it is possible to get sum=9 using subset={8,1}

Also, learn these tutorials,

 

Leave a Reply

Your email address will not be published. Required fields are marked *