LeetCode 416: Partition Equal Subset Sum ·

基本資料
#

難易度: medium 第一次嘗試：2026-08-23 來源：Day 43 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 416 is the clean 0/1 reachability anchor.
I do not classify knapsack problems by surface wording alone. I ask three things: can each item be reused, what exactly does dp[...] represent, and what loop direction preserves that meaning in 1D compression. LC 416 is 0/1 reachability so the target loop goes backward. LC 518 is unbounded counting so the amount loop goes forward. LC 322 is also unbounded, but its state is minimum coins, so the recurrence and invalid-state handling are different.
explain LC 416 as 0/1 reachability with backward loop direction

當天筆記摘錄
#

Problem 1 - LC 416 Partition Equal Subset Sum
#

Pattern: 0/1 knapsack / subset-sum reachability

Why This Fits
#

Each number can be used:

either once or not at all

The question becomes:

can I reach total / 2?

That is classic 0/1 subset selection.

Core State / Invariant
#

2D form:

dp[i][s] = whether some subset from the first i numbers can make sum s

Compressed form:

dp[s] = whether the numbers processed so far can make sum s

Base Case
#

dp[0] = true

Reason:

choosing nothing always makes sum 0

Transition
#

For each num:

dp[s] = dp[s] or dp[s - num]

when:

s >= num

Why Loop Direction Matters
#

In 1D compression, iterate s backward:

for s from target down to num

Reason:

backward iteration prevents the current number from being reused in the same round

Complexity
#

Time: O(n * target)
Space: O(target)

Common Mistakes
#

forgetting the odd-total early exit
iterating s forward and accidentally reusing one number in the same round
saying dp[s] is a best value instead of a reachable-state boolean
failing to explain why dp[0] = true

Strong Spoken Explanation
#

I first reduce the problem to whether some subset reaches total / 2, because equal partition means both sides must sum the same. Then I use 0/1 subset-sum DP where dp[s] means whether the processed numbers can make sum s. The base case is dp[0] = true, since choosing nothing makes sum zero. For each number I update the target sum backward so the current number is used at most once. If dp[target] is true at the end, an equal partition exists.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True

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

        return dp[target]