Subset sum problem

In the subset sum problem, we are given a list of all positive numbers and a Sum. We need to check if there is a subset whose sum is equal to the given sum.

Example

Input

List of numbers: 1 2 3 10 5

sum: 9

Output

 true

Explanation

 for a subset {1,3,5} sum of all values (1+3+5) = 9 ,which is equal to the given sum. So our answer is yes.

Approach for Subset sum problem

• For each element in the given list, we have two options.

1. To include the element in the subset
2. To exclude the element from the subset.

•  If we include the element in the subset then the value of sum decreases by the value of the element.
• If we excluded the element the value of sum remains the same.
• After repeating these steps for each element if the value of sum decreases to zero then definitely we have a subset whose sum is equal to the given sum and we return true.
• Otherwise, we return false.

Recursive solution

 C++ code

#include <stdio.h> 
bool check(int a[], int n, int sum) 
{ 
if (sum == 0) 
  return true; 
if (n == 0 && sum != 0) 
  return false; 
if (a[n-1] > sum) 
  return check(a, n-1, sum); 
return check(a, n-1, sum) || 
            check(a, n-1, sum-a[n-1]); 
} 
int main() 
{ 
int a[] = {3, 34, 4, 12, 5, 2}; 
int sum = 9; 
int n = sizeof(a)/sizeof(a[0]); 
if (check(a, n, sum) == true) 
  printf("Found"); 
else
  printf("Not found"); 
return 0; 
}

Found

Java code

class subset { 
  
  static boolean check(int a[], 
              int n, int sum) 
  { 
    if (sum == 0) 
      return true; 
    if (n == 0 && sum != 0) 
      return false; 
    if (a[n-1] > sum) 
      return check(a, n-1, sum); 
    return check(a, n-1, sum) || 
      check(a, n-1, sum-a[n-1]); 
  } 
  public static void main (String args[]) 
  { 
    int a[] = {3, 34, 4, 12, 5, 2}; 
    int sum = 9; 
    int n = a.length; 
    if (check(a, n, sum) == true) 
      System.out.println("Found"); 
    else
      System.out.println("Not found"); 
  } 
}

Found

Complexity analysis for Subset sum problem

Time complexity

The recursive approach will check all possible subset of the given list. So, the time complexity will be exponential.

Dynamic programming approach for Subset sum problem

The recursive approach will check all possible subset of the given list. The subproblem calls small calculated subproblems many times. So to avoid recalculation of the same subproblem we will use dynamic programming. We will memorize the output of a subproblem once it is calculated and will use it directly when we need to calculate it again. The time complexity of the dynamic programming approach is O(n*sum).

C++ code

bool check(int a[], int n, int sum) 
{ 
  bool subset[n+1][sum+1]; 
  for (int i = 0; i <= n; i++) 
  subset[i][0] = true; 
  for (int i = 1; i <= sum; i++) 
  subset[0][i] = false; 
  for (int i = 1; i <= n; i++) 
  { 
  for (int j = 1; j <= sum; j++) 
  { 
    if(j<a[i-1]) 
    subset[i][j] = subset[i-1][j]; 
    if (j >= a[i-1]) 
    subset[i][j] = subset[i-1][j] || 
                subset[i - 1][j-a[i-1]]; 
  } 
  } 
  
  return subset[n][sum]; 
} 

int main() 
{ 
int a[] = {3, 34, 4, 12, 5, 2}; 
int sum = 9; 
int n = sizeof(a)/sizeof(a[0]); 
if (check(a, n, sum) == true) 
  printf("Found"); 
else
  printf("Not found"); 
return 0; 
}

Found

Java code

class checksubset { 
  static boolean check(int a[], 
              int n, int sum) 
  { 
    boolean subset[][] = 
          new boolean[sum+1][n+1]; 
    for (int i = 0; i <= n; i++) 
      subset[0][i] = true; 
    for (int i = 1; i <= sum; i++) 
      subset[i][0] = false; 
    for (int i = 1; i <= sum; i++) 
    { 
      for (int j = 1; j <= n; j++) 
      { 
        subset[i][j] = subset[i][j-1]; 
        if (i >= a[j-1]) 
        subset[i][j] = subset[i][j] || 
          subset[i - a[j-1]][j-1]; 
      } 
    } 
  
  
    return subset[sum][n]; 
  } 
  public static void main (String args[]) 
  { 
    int a[] = {3, 34, 4, 12, 5, 2}; 
    int sum = 9; 
    int n = a.length; 
    if (check(a, n, sum) == true) 
      System.out.println("Found"); 
    else
      System.out.println("Not found"); 
  } 
}

Found

Complexity analysis for Subset sum problem

Time complexity

O(sum*n) here the sum is given sum and n is the number of elements in the array. We are traversing the 2D matrix to solve the problem and the answer is obtained at the bottom right corner of the matrix.

Space complexity

O(sum*n) We are using a 2D array for memorization.

References