• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Subset Sum Problem Dynamic programming

January 23, 2018 by Dhaval Dave

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.

Example

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*2n) 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}

DP table

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.

 

Similar Articles

Filed Under: Adobe Interview Questions, Algorithm, Amazon Interview Question, Array, Data Structure, Flipkart Interview Questions, Interview Questions Tagged With: Array, Dynamic Programming

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Amazon Interview Experience – SDE Chennai

simple sql injection

Python List

SAP Interview Questions

SAP Off Campus Hiring_ March 2015 Verbal Skills

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Convert number to words java

ADOBE Aptitude C Language Test

Given a string, find the first character which is non-repetitive

Length of the longest substring without repeating characters

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Apriori algorithm C Code Data Mining

Maximum occurred Smallest integer in n ranges

The Magic HackerEarth Nirvana solutions Hiring Challenge

Find Pythagorean Triplets in an array in O(N)

Diagonal Traversal of Binary Tree

Python String and numbers

Minimum insertions to form a palindrome

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Generate largest number arranging a no. of given non negative integer numbers

Reliance Jio Software Developer Interview Experience

System Design: Designing a LLD for Hotel Booking

Wrong Directions given find minimum moves so that he can reach to the destination

Find the smallest window in a string containing all characters of another string

Skiing on Mountains Matrix

Generate next palindrome number

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Practo Hiring Experience

FizzBuzz Solution C C++

Find if a binary tree is height balanced ?

Copyright © 2025 · Genesis Framework · WordPress · Log in