Subset Sum Problem

Subset Sum Problem

Problem Statement

Given an array of non-negative integers and an integer sum. We have to tell whether there exists any subset in an array whose sum is equal to the given integer sum.

Examples:

Input: arr[] = {3, 34, 4, 12, 3, 2}, sum = 7
Output: True
Explanation: There is a subset (4, 3) with sum 7.

Input: arr[] = {2, 2, 2, 3, 2, 2}, sum = 10
Output: True
Explanation:

Problem Statement Example

Recursive Approach

For this approach, we have two cases. 

  • Let’s take the last element and now the sum = target sum – value of ‘last’ element and elements remaining = size of array – 1.
  • Now  don’t take the ‘last’ element and now the  sum = target sum and elements remaining = size of array – 1.

Dry Run of the Approach:

Suppose n is the size of the array.

isThereSubsetSum(arr, n, sum) = isThereSubsetSum(arr, n-1, sum) ||  isThereSubsetSum(arr, n-1, sum-arr[n-1])

Base Cases

isThereSubsetSum(arr, n, sum) = false, if sum > 0 and n == 0
isThereSubsetSum(arr, n, sum) = true, if sum == 0

Dry Run of Recursive Approach

C Implementation Of Recursive Approach

bool isThereSubsetSum(int arr[], int n, int sum) {
  if (sum == 0)
    return true;
  if (n == 0)
    return false;

  if (arr[n - 1] > sum)
    return isThereSubsetSum(arr, n - 1, sum);

  return isThereSubsetSum(arr, n - 1, sum) ||
    isThereSubsetSum(arr, n - 1, sum - arr[n - 1]);
}

Java Implementation Of Recursive Approach

static boolean isThereSubsetSum(int arr[],
  int n, int sum) {

  if (sum == 0)
    return true;
  if (n == 0)
    return false;

  if (arr[n - 1] > sum)
    return isThereSubsetSum(arr, n - 1, sum);

  return isThereSubsetSum(arr, n - 1, sum) ||
    isThereSubsetSum(arr, n - 1, sum - arr[n - 1]);
}

Python Implementation Of Recursive Approach

def isThereSubsetSum(arr, n, sum):
    if (sum == 0):
        return True
    if (n == 0):
        return False
 
    if (arr[n - 1] > sum):
        return isThereSubsetSum(arr, n - 1, sum)
 
    return isThereSubsetSum(
        arr, n-1, sum) or isThereSubsetSum(
        arr, n-1, sum-arr[n-1])

Time complexity: The above approach may try all the possible subsets of a given array in the worst case. Therefore the time complexity of the above approach is exponential.


Dynamic Programming Approach

In this approach, we will make a 2D array of size equal to (size of array + 1) * (target sum + 1) of boolean type. The state dp[i][j] will be true if there is a subset of elements from A[0….i] with a sum value equal to j.

Approach:

  • We make a boolean dp[][] and fill it in a top-down manner.
  • The value of dp[i][j] will be true if there exists a subset of dp[0..i] with a sum equal to j., otherwise false
  • Finally, we return dp[n][sum]

C Implementation For Subset Sum

bool isThereSubsetSum(int arr[], int n, int sum) {

  bool dp[n + 1][sum + 1];
  for (int i = 0; i <= n; i++)
    dp[i][0] = true;

  for (int i = 1; i <= sum; i++)
    dp[0][i] = false;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= sum; j++) {
      if (j < arr[i - 1])
        dp[i][j] = dp[i - 1][j];
      if (j >= arr[i - 1])
        dp[i][j] = dp[i - 1][j] ||
        dp[i - 1][j - arr[i - 1]];
    }
  }
  return dp[n][sum];
}

Java Implementation For Subset Sum

static boolean isThereSubsetSum(int arr[], int n, int sum) {
  boolean dp[][] = new boolean[n + 1][sum + 1];
  for (int i = 0; i <= n; i++)
    dp[i][0] = true;

  for (int i = 1; i <= sum; i++)
    dp[0][i] = false;

  for (int i = 1; i <= sum; i++) {
    for (int j = 1; j <= n; j++) {
      if (j < arr[i - 1])
        dp[i][j] = dp[i - 1][j];
      if (j >= arr[i - 1])
        dp[i][j] = dp[i - 1][j] ||
        dp[i - 1][j - arr[i - 1]];
    }
  }
  return dp[n][sum];
}

Python Implementation For Subset Sum

def isThereSubsetSum(arr, n, sum):
     
    dp =([[False for i in range(sum + 1)]
            for i in range(n + 1)])
     
    for i in range(n + 1):
        dp[i][0] = True
         
    for i in range(1, sum + 1):
         dp[0][i]= False
             
   
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if j<arr[i-1]:
                dp[i][j] = dp[i-1][j]
            if j>= arr[i-1]:
                dp[i][j] = (dp[i-1][j] or
                                dp[i - 1][j-arr[i-1]])
     
    return dp[n][sum]

Time Complexity: O(N * sum) where N is the size of the array.
Space Complexity: O(N * sum) where N is the size of the array.


Practice Questions

Minimum Difference Subsets
Subset Sum Problem
Equal Average Partition
Dynamic Programming


Frequently Asked Questions

What subset sum problem gives a suitable example?
The Subset-Sum Problem is to find a subset’ of the given array A = (A1 A2 A3…An) where the elements of the array A are n positive integers in such a way that a’∈A and summation of the elements of that subsets is equal to some positive integer S.

Is the subset sum problem NP-hard?
Yes, it is an NP-hard problem.

Is subset-sum an optimization problem?
Yes, subset-sum is an optimization problem because it has a variety of algorithms for tackling it.

How do you solve subsets?
Subsets can be solved using backtracking and dynamic programming with efficient time complexity.

Previous Post
Find the Missing Number

Find The Missing Number

Next Post
Trapping Rain Water

Trapping Rain Water

Total
0
Share