Lesson 51 — DP V: 0/1 knapsack

~25 minutes · Day 65 · dynamic programming

Tonight's interview shape is Partition Equal Subset Sum: given positive integers, decide whether they can be split into two groups with the same total. The trick is not to build the two groups directly. The trick is to ask whether one group can hit the exact half-sum.

The invariant

Ask “can some subset hit this exact target?” where target = totalSum/2; each item is usable once, so sweep targets from high to low.

That sentence is the pattern. If the total sum is odd, there is no equal split. If the total sum is even, the whole problem becomes one yes/no question: can some subset make totalSum / 2?

Partition: the slow way first

The brute force is to try every subset: take or skip each number, then check whether one path reaches the target. That is O(2^n) time because every item doubles the number of possibilities. It is correct, but it grows too fast for interview input sizes.

def brute(nums, i, target):
    if target == 0: return True
    if i == len(nums) or target < 0: return False
    return brute(nums, i + 1, target - nums[i]) or brute(nums, i + 1, target)

Dynamic programming keeps the useful part of that recursion: the reachable sums. Instead of asking the same “can I make sum s?” question again and again, store each answer in a boolean array.

Partition: the DP way

Use the four DP questions from the training plan:

• State: dp[s] means some processed subset can make sum s.
• Transition: after seeing x, sum s is reachable if it already was, or if s - x was reachable.
• Base: dp[0] = True, because the empty subset makes zero.
• Answer: return dp[target].

def canPartition(nums):
    total = sum(nums)                         # Python's built-in sum
    if total % 2 == 1:
        return False                          # odd total cannot split evenly
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True                              # empty subset makes 0
    for x in nums:
        for s in range(target, x - 1, -1):    # high to low: use x once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

sum gives the total, and range can count downward with a negative step. The high-to-low sweep is the part to protect. If you sweep upward, dp[s - x] might have been created by the same x, which accidentally turns a 0/1 choice into an unlimited-use choice.

The state space

Transfer: same question, new costume

Suppose the question is smaller: with nums = [2, 3, 7, 8], can some subset hit target 10? Before opening the reveal, say the state, transition, base case, and answer location out loud.

What the trade buys you

The trade is memory for repeated work. The boolean row remembers which sums are reachable, so each item updates each target once.

Practice — answer before you scroll past

for x in nums:
    for s in range(x, target + 1):
        dp[s] = dp[s] or dp[s - x]

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Partition Equal Subset Sum — predict the half-sum target, attempt the high-to-low DP, compare after your attempt, then encode the invariant in your own words.

For the encode step, write four short sentences: state, transition, base case, answer location. That is the DP self-check gate for this lesson.