Subset Sum Problem

Problem Statement

Given a set of non-negative integers and a target sum, determine if there is a subset of the given set whose sum equals the target sum.

Example:

• Input: set = [3, 34, 4, 12, 5, 2], sum = 9
• Output: true (subset 5 sums to 9)

Noob-Friendly Explanation

Imagine you have a handful of coins: ₹3, ₹34, ₹4, ₹12, ₹5, ₹2. Can you pick some of these coins so they add up to exactly ₹9? You don't have to use all coins — just find any group that totals 9. Here, ₹4 + ₹5 = ₹9 works! The problem is simply: "Can I pick a group from these numbers that adds up to my target?"

Approach 1: Brute Force (Recursion)

Intuition

For each element, you have two choices: include it in the subset or exclude it. Try all combinations and check if any subset sums to the target.

Algorithm

1. If target sum is 0, return true (empty subset works)
2. If no elements left and sum is not 0, return false
3. If the last element is bigger than the sum, skip it
4. Otherwise, check both: include it or exclude it

public class Solution {
    public boolean isSubsetSum(int[] set, int n, int sum) {
        // Sum 0 can always be achieved (empty subset)
        if (sum == 0) return true;

        // No elements left
        if (n == 0) return false;

        // If last element is more than sum, skip it
        if (set[n - 1] > sum) {
            return isSubsetSum(set, n - 1, sum);
        }

        // Check including or excluding the last element
        return isSubsetSum(set, n - 1, sum - set[n - 1])
            || isSubsetSum(set, n - 1, sum);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Each element has 2 choices
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (Bottom-Up DP)

Intuition

Build a 2D boolean table where dp[i][j] is true if a subset of the first i elements can sum to j. We fill it row by row.

Algorithm

1. Create dp[n+1][sum+1], set dp[i][0] = true for all i (sum 0 is always possible)
2. For each element i and each target j:
   • dp[i][j] = dp[i-1][j] (exclude the element)
   • If set[i-1] <= j, also check dp[i][j] = dp[i][j] || dp[i-1][j - set[i-1]]
3. Answer is dp[n][sum]

public class Solution {
    public boolean isSubsetSum(int[] set, int n, int sum) {
        boolean[][] dp = new boolean[n + 1][sum + 1];

        // Sum 0 is always achievable
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                // Don't include current element
                dp[i][j] = dp[i - 1][j];

                // Include current element if it fits
                if (set[i - 1] <= j) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - set[i - 1]];
                }
            }
        }

        return dp[n][sum];
    }
}

Complexity Analysis

• Time Complexity: O(n * sum) - Fill each cell of the n × sum table
• Space Complexity: O(n * sum) - The 2D DP table