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 = 7

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