Subset Sum Problem

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to the given sum.

Examples

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

Input: values[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.

Problem Identification

When you see an algorithmic problem, the first thing you should do is try to identify patterns in the problem statement so that you can relate it to the patterns you have already learned and then try to solve it using that pattern. Algorithmic problems are unlimited but there are only a finite set of patterns and approaches to solve those problems.

All right, So looking at the problem statement, we can notice the following things:

We’re given a number of items
We have choices - include a value in the subset or don’t.
We have a target sum.

Do these clues ring a bell? Well, it’s a variant of the 0-1 Knapsack problem. Read about the 0-1 Knapsack pattern. In this case, we’re not given the weight of the items, the item values themselves are weights.

Recursive Solution

All right! So following the same Knapsack problem approach, let’s build a simple choice diagram for our problem so that we can come up with the recursive solution.

For every given integer (value), we have two options

                 [value]
                /       \  
value > targetSum       value <= targetSum

if value > targetSum; We can’t include this item in the subset. We don’t have a choice
if value <= targetSum; We have a choice to either include this item in the subset or don’t. Whichever choice leads us to the target sum will be chosen.

Let’s now try to devise a recursive structure for our problem. Let’s say that SubsetSum(S, n) is a boolean that represents whether we can obtain a target sum of S using the values from index 1..n or not.

Recursive structure

For every item, we have two choices - either include this item in the subset or don’t. We will consider both the choices and determine if we can find a subset of sum S using any of the choices or not.

There will be a subset of sum S using values from index 1..n if

we can find a subset of sum S using values from index 1..n-1 (Excluding the nth item)
or
we can find a subset of sum S-values[i] using values from index 1..n-1 (Including the nth item)

If the value of the nth item is greater than the target sum S then we can’t include this item in the subset and choice 1 is the only possibility. Let’s write our recursive structure mathematically:

SubsetSum(S, n) = SubsetSum(S, n-1); if values[n] > S
SubsetSum(S, n) = SubsetSum(S, n-1) || SubsetSum(S - values[n], n-1); if values[n] <= S

Base condition

To identify the base condition of recursion, think about the smallest valid input (Empty value array or Zero sum)

SubsetSum(S, 0) = false; for S > 0 // We can't obtain a positive sum with no items
SubSetSum(0, n) = true; for any value of n // We can obtain a zero sum by not choosing any items and having an empty subset

Allright! Let’s now write the code for our recursive solution

import java.util.Scanner;

public class SubsetSumRecursion {
    private static boolean hasSubsetSum(int[] values, int targetSum, int n) {
        if (targetSum == 0) {
            return true;
        }
        if (n == 0) {
            return false;
        }

        if (values[n - 1] > targetSum) {
            return hasSubsetSum(values, targetSum, n - 1);
        }

        return hasSubsetSum(values, targetSum - values[n - 1], n - 1)
                || hasSubsetSum(values, targetSum, n - 1);
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();

        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = keyboard.nextInt();
        }

        int target = keyboard.nextInt();
        keyboard.close();

        System.out.println("Has Subset sum: " + hasSubsetSum(values, target, n));
    }
}

$ javac SubsetSumRecursion.java
$ java SubsetSumRecursion
6
3 34 4 12 5 2
9
Has Subset sum: true

Time Complexity: O(2^n) , Exponential. Learn how to do time complexity analysis for recursive functions

Space Complexity: O(1), no additional space reserved. Only Stack space is used in recursion.

Method 2: Dynamic Programming Top down solution (Memoization)

We can use dynamic programming to memoize the solutions to subproblmes. Following is the memoized dynamic programming solution.

import java.util.Scanner;

public class SubsetSumTopDown {
    private static Boolean[][] subsetSumMem;

    private static boolean hasSubsetSumRecur(int[] values, int targetSum, int n) {
        if (targetSum == 0) {
            return true;
        }
        if (n == 0) {
            return false;
        }

        if (subsetSumMem[targetSum][n] != null) {
            return subsetSumMem[targetSum][n];
        }

        if (values[n - 1] > targetSum) {
            subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum, n - 1);
        } else {
            subsetSumMem[targetSum][n] = hasSubsetSumRecur(values, targetSum - values[n - 1], n - 1)
                    || hasSubsetSumRecur(values, targetSum, n - 1);
        }

        return subsetSumMem[targetSum][n];
    }

    private static boolean hasSubsetSumMemoized(int[] values, int targetSum, int n) {
        subsetSumMem = new Boolean[targetSum + 1][n + 1];
        for (int s = 0; s <= targetSum; s++) {
            for (int i = 0; i <= n; i++) {
                subsetSumMem[s][i] = null;
            }
        }
        return hasSubsetSumRecur(values, targetSum, n);
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = keyboard.nextInt();
        }
        int target = keyboard.nextInt();

        keyboard.close();

        System.out.println("Has Subset sum: " + hasSubsetSumMemoized(values, target, n));
    }
}

Method 3: Dynamic Programming Bottom up solution

import java.util.Scanner;

public class SubsetSumBottomUp {
    private static boolean hasSubsetSum(int[] values, int targetSum) {
        int n = values.length;
        boolean[][] subsetSum = new boolean[targetSum + 1][n + 1];
        subsetSum[0][0] = true;

        for (int i = 1; i <= targetSum; i++) {
            for (int j = 1; j <= n; j++) {
                if (values[j - 1] > i) {
                    subsetSum[i][j] = subsetSum[i][j - 1];
                } else {
                    subsetSum[i][j] = subsetSum[i - values[j - 1]][j - 1] || subsetSum[i][j - 1];
                }
            }
        }

        return subsetSum[targetSum][n];
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = keyboard.nextInt();
        }
        int target = keyboard.nextInt();

        keyboard.close();

        System.out.println("Has Subset sum: " + hasSubsetSum(values, target));
    }
}

Dynamic Programming