Home » Technical Interview Questions » Dynamic Programming Interview Questions » Subset Sum Problem in O(sum) space

Subset Sum Problem in O(sum) space


Reading Time - 6 mins


Difficulty Level Easy

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

Subset Sum Problem in O(sum) space

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?

READ  Maximum sum bitonic subarray

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.

READ  Number Of Longest Increasing Subsequence

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions