Table of Contents
Problem Statement
The “Subset sum in O(sum) space” problem states that you are given an array of some non-negative integers and a specific value. Now find out if there is a subset whose sum is equal to that of the given input value.
Example
Array = {1, 2, 3, 4}
targetSum = 7The subset having sum equal to given input is possible
Approach for Subset Sum Problem in O(sum) space
The simplest approach which anyone can think of is to create all subsets and take their sum. Now check if this sum is equal to the given input sum, right? The approach is correct. There’s no doubt about that. But there is one problem, we can not create all the subsets efficiently. The creation of subsets itself has O(2^N) time complexity. So, we must think of some other efficient way to solve the problem.
Okay, so let’s think of this problem in this way. We know that there are some subsets having some sums. Now for the current element, we have two options either we add it to the already present subsets or we don’t ad it into the subsets. So, now we know what we need to do. To summarise it, we will run a loop over the sums (that is on the values from 1 to input sum). Since this is getting a bit confusing. We call the input sum as “Target’ and the sums on which have to traverse. We will represent them with “i”. And for each i, we check if don’t take the current element, “Do we have a subset having sum equal to i?”. Or if we take this current element can we make total sum equal to that of i? So we can rephrase this last statement. If we subtract the value of the current element from i, do we have a subset having a sum equal to that of i-current element?
So, now we just need to find if we can form a subset having sum equal to i or equal to i-current element.
Now how to solve it? We will use Dynamic Programming to solve this problem. we will create a 2D array or a matric whose [i,j] cell is true if we can get a subset having sum equal to j using elements from 0 to i. Otherwise, it is false.
Recursive formula
dp[i][j] = dp[i-1][j] | dp[i-1][j-input[i]]
From the recursive formula, we get to know that the current row is dependent only on the last row. So we can get away with keeping only two rows instead of n rows for n elements. One row will act like a row for the last element and the other for the current element. This is a well known DP optimization.
Code
C++ code for Subset Sum Problem in O(sum) space
#include<bits/stdc++.h>
using namespace std;
#include <stdio.h>
#include <stdbool.h>
bool findSubset(int arr[], int n, int targetSum)
{
// dp array to store if any sum is possible
bool dp[2][targetSum + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= targetSum; j++) {
// subset with sum equal to zero is always possible
// we don't choose any element
if (j == 0)
dp[i % 2][j] = true;
// j != 0 and i ==0
else if (i == 0)
dp[i % 2][j] = false;
// current element is greater than the current value of sum(j)
// so take OR of two conditions
// 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
// 2. We don't take the current element
else if (arr[i - 1] <= j)
dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j];
// Here we cannot take the current element
// So simply check is such a subset is possible
else
dp[i % 2][j] = dp[(i + 1) % 2][j];
}
}
return dp[n % 2][targetSum];
}
int main(){
// Number of elements
int n;cin>>n;
// array to store non-negative numbers
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int targetSum;
cin>>targetSum;
bool can = findSubset(a, n, targetSum);
if(can == true)
cout<<"The subset having sum equal to given input is possible";
else
cout<<"None of the subsets have sum equal to given input";
}
4 1 2 3 4 6
The subset having sum equal to given input is possible
Java code for Subset Sum Problem in O(sum) space
import java.util.*;
class Main{
static boolean findSubset(int arr[], int n, int targetSum)
{
// dp array to store if any sum is possible
boolean dp[][] = new boolean[2][targetSum + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= targetSum; j++) {
// subset with sum equal to zero is always possibe
// we don't choose any element
if (j == 0)
dp[i % 2][j] = true;
// j != 0 and i ==0
else if (i == 0)
dp[i % 2][j] = false;
// current element is greater than the current value of sum(j)
// so take OR of two conditions
// 1. Take the current element check if we can get a subset having sum = j-arr[i-1]
// 2. We don't take the current element
else if (arr[i - 1] <= j)
dp[i % 2][j] = dp[(i + 1) % 2][j - arr[i - 1]] || dp[(i + 1) % 2][j];
// Here we cannot take the current element
// So simply check is such a subset is possible
else
dp[i % 2][j] = dp[(i + 1) % 2][j];
}
}
return dp[n % 2][targetSum];
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
// Number of elements
int n = sc.nextInt();
// array to store non-negative numbers
int a[] = new int[n];
for(int i=0;i<n;i++)
a[i] = sc.nextInt();
int targetSum = sc.nextInt();
boolean can = findSubset(a, n, targetSum);
if(can == true)
System.out.println("The subset having sum equal to given input is possible");
else
System.out.println("None of the subsets have sum equal to given input");
}
}4 1 2 3 4 6
The subset having sum equal to given input is possible
Complexity Analysis
Time Complexity
O(Sum*N), because we have traversed over all the elements and checked for each value of sum from 0 to given input sum that whether it is possible or not? So the time complexity is polynomial.
Space Complexity
O(Sum), because we have not used rows for each element. Instead of doing that we have simply just used two rows to store intermediate results for the current and last element. Thus space complexity is linear.