Subset Sum

Problem Link: Subset Sum Problem - GFG

Problem Statement

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

Solution Flow

1. Recursion (Pick-Not Pick)

Intuition: For each element, decide whether to include it or exclude it.

Base Cases:

• If sum == 0: return true

• If n == 0 && sum > 0: return false

Java Code:

class Solution {
    static Boolean isSubsetSum(int n, int arr[], int sum) {
        if (sum == 0) return true;
        if (n == 0) return false;

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

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

Complexity:

• Time: O(2^n)

• Space: O(n)

2. Memoization (Top-Down DP)

DP Definition: dp[i][s] = true if sum s can be formed using first i elements.

Java Code:

class Solution {
    static Boolean isSubsetSum(int n, int arr[], int sum) {
        Boolean[][] dp = new Boolean[n + 1][sum + 1];
        return solve(n, arr, sum, dp);
    }

    static Boolean solve(int n, int arr[], int sum, Boolean[][] dp) {
        if (sum == 0) return true;
        if (n == 0) return false;
        if (dp[n][sum] != null) return dp[n][sum];

        if (arr[n - 1] > sum) 
            dp[n][sum] = solve(n - 1, arr, sum, dp);
        else 
            dp[n][sum] = solve(n - 1, arr, sum, dp) || 
                         solve(n - 1, arr, sum - arr[n - 1], dp);

        return dp[n][sum];
    }
}

Complexity:

• Time: O(n * sum)

• Space: O(n * sum)

3. Tabulation (Bottom-Up DP)

Initialization:

• dp[i][0] = true (sum 0 always possible)

• dp[0][s] = false for s > 0

Java Code:

class Solution {
    static Boolean isSubsetSum(int n, int arr[], 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 <= n; i++) {
            for (int s = 1; s <= sum; s++) {
                if (arr[i - 1] > s) 
                    dp[i][s] = dp[i - 1][s];
                else 
                    dp[i][s] = dp[i - 1][s] || dp[i - 1][s - arr[i - 1]];
            }
        }
        return dp[n][sum];
    }
}

Dry Run (arr = [3, 4, 5], sum = 7)

| i ↓ \ s → | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   |
|-----------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0         | T   | F   | F   | F   | F   | F   | F   | F   |
| 1         | T   | F   | F   | T   | F   | F   | F   | F   |
| 2         | T   | F   | F   | T   | T   | F   | F   | T   |
| 3         | T   | F   | F   | T   | T   | T   | T   | T   |

Result: dp[3][7] = true

4. Space Optimization (1D DP)

Java Code:

class Solution {
    static Boolean isSubsetSum(int n, int arr[], int sum) {
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int i = 0; i < n; i++) {
            for (int s = sum; s >= arr[i]; s--) {
                if (dp[s - arr[i]]) 
                    dp[s] = true;
            }
        }
        return dp[sum];
    }
}

Dry Run

Initial:     [T, F, F, F, F, F, F, F]

After 3:     [T, F, F, T, F, F, F, F]

After 4:     [T, F, F, T, T, F, F, T]

After 5:     [T, F, F, T, T, T, F, T]

Result: dp[7] = true

Key Takeaways

1. Recursive → Memoized → Tabulated → Space-Optimized

2. Subset Sum ⊆ 0/1 Knapsack

3. Reverse iterate in 1D DP to avoid overwriting required states.

4. Always initialize dp[0] = true (sum 0 is always possible).