Solving Subset-Sum with 0/1 Dynamic Programming

Hello! In our previous lesson, we saw how dynamic programming could be applied to 2D grids to count paths or find minimum costs. You learned to define a state dp[i][j] based on grid coordinates and formulate a transition based on allowed moves.

Today, we shift our focus to another fundamental and powerful application of DP: solving subset problems. Our learning outcome is to solve a subset-sum decision problem with zero-one dynamic programming. This pattern is the foundation for a whole category of optimization problems often disguised in interview questions, like the famous "Knapsack problem". We will start from a simple recursive idea and build our way up to an efficient, space-optimized DP solution.

The Subset Sum Problem

The core problem is straightforward: given a set of positive integers and a target sum, can you find a subset of those integers that adds up exactly to the target?

For example, given the set {3, 1, 4, 5} and a target of 7, the answer is true because the subset {3, 4} sums to 7. For a target of 11, the answer is false.

A common variant you'll see in interviews is the "Partition Equal Subset Sum" problem (LeetCode 416). It asks if you can partition a set into two subsets with an equal sum. This is just a clever disguise for the subset sum problem. If such a partition is possible, the total sum of the original set must be even, and each subset's sum must be exactly half of the total. So, the problem reduces to: "Can we find a subset that sums to total_sum / 2?"

From Brute-Force Recursion to DP

How would we approach this from scratch? The most direct way is to try every possible subset. For each number in our set, we face a decision: do we include it in our subset, or do we exclude it?

This "choose-or-skip" logic naturally leads to a recursive solution. We can define a function that tries both paths for each number.

This recursive approach, often called backtracking, works but it's slow. Its time complexity is $O(2^n)$, where $n$ is the number of elements in the set, because the decision tree has $2^n$ leaves. As you've seen before, this exponential complexity often signals that we're re-computing the same subproblems. For example, we might repeatedly ask, "Can we make a sum of 5 with the last three elements?"

This is where dynamic programming comes in. We can use a table to store the results of these subproblems to avoid recalculating them.

Bottom-Up Tabulation for Subset Sum

Let's build a solution using the bottom-up tabulation method you're now familiar with. We'll solve the "Partition Equal Subset Sum" problem for the array nums = [1, 5, 11, 5].

1. Transform the problem: The total sum is 1 + 5 + 11 + 5 = 22. This is even. Our target sum for a subset is 22 / 2 = 11.
2. Define the State: We'll create a 2D table, dp[i][j], where i represents using the first i numbers from our input array, and j represents the target sum we are trying to achieve. dp[i][j] will be a boolean: true if a sum of j is possible using some of the first i numbers, and false otherwise. Our table will have n+1 rows and target+1 columns.
3. Identify the Base Cases:
   • dp[0][0] is true. We can achieve a sum of 0 with an empty set of numbers (by choosing nothing).
   • The first column (j=0) is all true. A sum of 0 is always achievable, regardless of how many numbers are available.
   • The first row (i=0, except for dp[0][0]) is all false. We cannot achieve a non-zero sum with no numbers.
4. Find the Transition: Now, how do we fill in dp[i][j]? Let's say the i-th number is num = nums[i-1]. We have two choices:
   • Exclude num: If we don't use num, then dp[i][j] is possible if and only if dp[i-1][j] was possible (i.e., we could already make sum j with the previous i-1 numbers).
   • Include num: We can only do this if j >= num. If we use num, we must have been able to form the remaining sum, j - num, using the previous i-1 numbers. So, we check dp[i-1][j-num].

Since we can achieve the sum by either excluding OR including the number, our transition is:

The || (OR) captures the logic that if either path leads to a solution, the result is true. This is a classic 0/1 dynamic programming recurrence, where for each item, you either take it (1) or you don't (0).

For a detailed explanation of this logic, the following resource is excellent. It covers the problem transformation, the DP state, the transition, and a full walkthrough.

To see this process animated, the following video provides a very clear, step-by-step visualization of filling out the DP table. The presenter's methodical approach can be very helpful for building intuition.

Here is a static view of a filled DP table for a similar problem. The arrows show the "traceback" path, which you could follow to reconstruct the subset (though the decision problem only asks for true/false).

Implementation and Space Optimization

A direct implementation of the 2D table is straightforward. Here is the TypeScript code that matches the logic we've discussed.

function canPartition(nums: number[]): boolean {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);

    if (totalSum % 2 === 1) {
        return false;
    }

    const target = totalSum / 2;
    const n = nums.length;

    // dp[i][j]: can we make sum j using first i elements?
    const dp: boolean[][] = Array(n + 1).fill(0).map(() => Array(target + 1).fill(false));

    // Base case: sum 0 is always possible
    for (let i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    // Fill the table
    for (let i = 1; i <= n; i++) {
        const num = nums[i - 1];
        for (let j = 1; j <= target; j++) {
            // Option 1: Don't include the current number
            const withoutNum = dp[i - 1][j];

            // Option 2: Include the current number (if possible)
            let withNum = false;
            if (j >= num) {
                withNum = dp[i - 1][j - num];
            }
            
            dp[i][j] = withoutNum || withNum;
        }
    }

    return dp[n][target];
}

This solution has a time complexity of $O(n\times \text{target})$ and a space complexity of $O(n\times \text{target})$. But can we do better on space?

Notice that to compute row i, we only ever need information from row i-1. We never look at i-2 or earlier. This is the exact same optimization opportunity we saw in the grid problems! We can reduce the space to just one array representing the previous row, bringing the space complexity down to $O(\text{target})$.

However, there's a subtle trap. If we use a single array dp and iterate the sums j from left to right (from 1 to target), when we calculate dp[j], the value dp[j - num] might have already been updated in this same pass. This would be like using the current num multiple times, which violates the 0/1 rule (we can only use each number once).

The solution is to iterate the inner loop backwards, from j = target down to num. This ensures that when we calculate dp[j] by looking at dp[j - num], the value dp[j - num] is still from the previous state (before we considered the current num).

This space-optimized approach is the standard, efficient solution for this problem. The following resource explains this optimization clearly.

Conclusion

You have now added another essential DP pattern to your toolkit. The 0/1 subset/knapsack pattern is incredibly versatile and appears in many forms.

Here are the key takeaways:

• Problem Recognition: Problems asking to partition a set or find a subset with a specific property can often be solved with DP. Look for the "Partition Equal Subset Sum" pattern, which reduces to subset sum.
• State Definition: The DP state dp[i][j] for subset problems typically answers a boolean question: "Is it possible to achieve property j (e.g., a sum) using the first i items?"
• 0/1 Transition: The transition embodies the "choose-or-skip" decision. The result for dp[i][j] is a combination (usually an OR) of the outcome from excluding the i-th item (dp[i-1][j]) and including it (dp[i-1][j - value]).
• Space Optimization: Subset sum problems can be optimized from $O(n\times \text{target})$ space to $O(\text{target})$ by using a 1D DP array and iterating the inner (sum) loop backwards.

In our next lesson, we will tackle our final DP pattern in this module: computing the longest common subsequence of two strings. This will take us back to a 2D DP table, but with a new kind of state and transition that compares two inputs simultaneously.