Subset Sum Problem

Intuition

Boolean DP: dp[j] = true if a subset with sum j exists. Same as 0/1 knapsack boolean version. For each element, iterate backwards through dp array.

Algorithm

1dp[0]=true, rest=false.
2For each num: for j from sum down to num: dp[j] |= dp[j-num].
3Return dp[sum].

Example Walkthrough

Input: arr=[3,34,4,12,5,2], sum=9

1.Subsets summing to 9: {4,5}, {3,4,2}. Return true.

Output: true

Common Pitfalls

•Process in reverse order (j from sum down) to avoid using an element multiple times.

Subset Sum Problem.java

Java

// Approach: DP. dp[j] = can we achieve sum j? For each element, iterate sum from high to low and set dp[j] |= dp[j-num].
// Time: O(n * sum) Space: O(sum)
class Solution {

    static Boolean isSubsetSum(int arr[], int sum) {
        int[][] dp = new int[arr.length][10001];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++)
                dp[i][j] = -1;
        }

        return dfs(arr, 0, 0, sum, dp);
    }

    static Boolean dfs(int[] arr, int ind, int curSum, int sum, int[][] dp) {
        if (curSum == sum)
            return true;

        if (ind >= arr.length)
            return false;

        if (curSum > sum)
            return false;

        if (dp[ind][curSum] != -1)
            return dp[ind][curSum] == 1;

        boolean take = dfs(arr, ind + 1, arr[ind] + curSum, sum, dp);
        if (take) {
            dp[ind][curSum] = 1;
            return take;
        }
        boolean notTake = dfs(arr, ind + 1, curSum, sum, dp);
        dp[ind][curSum] = notTake == true ? 1 : 0;

        return notTake;
    }
}

Was this solution helpful?