I Tried Two Pointers on a DP Problem and Learned What "Subset" Actually Means

I've been working through coding problems that I can understand when reading solutions but struggle to solve on my own. This series is about breaking down the "why does this actually work" part. Not tutorials. Just honest breakdowns of where my thinking got stuck and what finally unstuck it.

The problem

LeetCode 416: Partition Equal Subset Sum. Given an array of positive integers, determine if you can split it into two subsets with equal sum.

My first instinct: use two pointers. One starting from the left, one from the right. Grow each window. Whichever side has the smaller sum, expand that pointer. When they meet, check if the sums are equal.

I even thought about sorting first to make the approach work better. It felt clean. It felt efficient. It was completely wrong.

Why two pointers don't work here

Take [2, 3, 5, 7, 1, 6]. Total is 24, so each subset needs to sum to 12. The answer is true: {5, 7} and {2, 3, 1, 6}.

Sorted: [1, 2, 3, 5, 6, 7]. Running two pointers from both ends, the sums land at 11 and 13. They never balance. But the valid partition exists. It just requires picking the 5 and 7 from the middle while leaving everything else.

Two pointers assume you're splitting at some dividing line. Everything left goes in one group, everything right goes in the other. But "subset" means you can cherry-pick from anywhere. The 5 and the 7 aren't adjacent in the sorted array, and they definitely aren't on the same side of any split point.

That distinction between "split at a point" and "pick from anywhere" is what I missed entirely.

The real question hiding inside this problem

Once the subset framing clicked, the problem simplified. If the total sum is S, each subset needs to be S/2. And if S is odd, you can stop immediately. You can't split an odd number into two equal integers.

So the problem reduces to: can I find any subset of nums that adds up to exactly S/2?

That's subset sum. And subset sum is a DP problem.

Starting with plain recursion

Before any DP, I wrote the simplest version. For each element, you have two choices: include it in the subset or skip it. Include means the remaining target shrinks by that element's value. Skip means the target stays the same.

def canReach(index, target):
    if target == 0:
        return True
    if index >= len(nums) or target < 0:
        return False

    include = canReach(index + 1, target - nums[index])
    skip = canReach(index + 1, target)
    return include or skip

The or is because we only need one path to work. If including element 3 eventually leads to a valid subset, we don't care what skipping it would have done.

This works. It's also slow. For [1, 5, 5, 11] with target 11, the recursion tree branches twice at every element. That's 2^n paths. But more importantly, some of those paths ask the same question. "Can I reach target 5 starting from index 3?" shows up from multiple branches. Pure recursion answers it every time from scratch.

Adding memoization

The fix is three lines. Before computing, check if you've seen this (index, target) pair before. After computing, store the result.

def canReach(index, target):
    if target == 0:
        return True
    if index >= len(nums) or target < 0:
        return False
    if (index, target) in memo:
        return memo[(index, target)]

    result = canReach(index + 1, target - nums[index]) or canReach(index + 1, target)
    memo[(index, target)] = result
    return result

Same recursion. Same logic. Just remembering answers. This is the top-down DP approach.

The bottom-up version (and where I got confused)

The array-based DP flips the approach. Instead of recursing and caching, you build a boolean array where dp[s] answers: "can I reach sum s with the elements I've processed so far?"

dp = [False] * (target + 1)
dp[0] = True

for num in nums:
    for s in range(target, num - 1, -1):
        if dp[s - num]:
            dp[s] = True

return dp[target]

I understood what the code does. I could trace through it. But the line dp[s - num] felt disconnected from anything I could reason about. In my previous DP problem (decode ways), dp[i] meant "position i in the string." The index was a location. Here, the index IS the sum. That shift messed with my mental model.

The cashier analogy

What made it click was thinking about making exact change.

You're a cashier. A customer owes you $11. You have coins worth $1, $5, $5, and $11. You can only use each coin once. Can you make exactly $11?

You start knowing you can make $0 (by using nothing). Then you pick up each coin one at a time and ask: "what new amounts can I make now?"

Before any coins: {0}
Pick up the $1 coin: everything I could make before, plus everything-plus-1. So {0, 1}.
Pick up the first $5 coin: {0, 1, 5, 6}.
Pick up the second $5 coin: {0, 1, 5, 6, 10, 11}.

11 is in the set. Done.

Each time you pick up a coin, the old amounts stay (that's skipping the coin) and new amounts appear (that's including it). The same two choices as the recursion, just expressed as a growing set of reachable values.

Now dp[s - num] has a natural reading: "I want to make $s. I'm holding a $num coin. Can I cover the rest?" If dp[s - num] is true, then yes, adding this coin gets me to $s.

The backwards loop

This was the other thing that felt arbitrary until I traced through what goes wrong without it.

Say dp = [True, False, False, ...] and you process the $1 coin. If you loop forwards (small to large):

s=1: dp[0] is True, so dp[1] = True. Fine.
s=2: dp[1] is True (you just set it), so dp[2] = True. Wait.
s=3: dp[2] is True (just set again), so dp[3] = True.

You used the $1 coin three times. You only have one.

The problem is you're reading values you wrote during the same round. Each "yes" you write feeds the next check, and the coin keeps getting reused.

Going backwards (large to small): when you set dp[s] = True, the values you read from (dp[s - num]) are at smaller indices. You already passed those indices. You haven't touched them this round. So you're always reading "yesterday's answers," not the ones you just wrote.

The mental image that stuck: backwards means each coin goes back in the drawer after you check it. You can't accidentally grab it again. Forwards means the coin stays on the counter, and you keep picking it up.

The cheatsheet

This generalizes to a simple rule:

Can each item be used only once? Loop backwards. This is 0/1 knapsack, partition subset sum, target sum.

Can items be reused? Loop forwards. This is coin change, unbounded knapsack, combination sum.

One question. One answer. That's the entire decision.

The complete solution

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False

        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            for s in range(target, num - 1, -1):
                if dp[s - num]:
                    dp[s] = True

        return dp[target]

What I got wrong along the way

My first attempt at the DP had dp[target - i] instead of dp[i - num]. The difference matters. dp[i - num] asks "was the sum that's num less than i reachable?" That's the include question: if I can reach 1, and I have a 5-coin, I can reach 6. My wrong version was asking a completely unrelated question about a completely unrelated index.

The fix came from going back to the cashier framing. "I want $6. I have $5. Can I cover the remaining $1?" That's dp[6 - 5]. Not dp[11 - 6].

What to practice next

These all use the same "items toward a target" DP pattern, ordered by difficulty:

1. LeetCode 494 (Target Sum): Same include/skip structure. Each element is either added or subtracted. The target just shifts.
2. LeetCode 322 (Coin Change): Unlimited reuse, so the loop goes forwards. Good for locking in the direction rule.
3. LeetCode 474 (Ones and Zeroes): 0/1 knapsack but with two dimensions (count of 0s and 1s). Same backwards loop, just a 2D array.
4. LeetCode 518 (Coin Change II): Counting combinations instead of just true/false. Forwards loop, addition instead of boolean OR.

I'm building Levelop to help people get better at problems like these. If you want more breakdowns like this, check it out.