分割等和子集 图解题解

这道题到底在问什么

nums

[1, 5, 11, 5]

总和/目标

22 / 11

输出

true （{11} 与 {1,5,5}）

先想最直接的笨办法

表头是目标和 0~11，每格是「能否凑出这个和」。dp[0]=✓（凑 0 肯定行，啥都不选），其余先全 ✗。下面把 nums 里的数 1、5、11、5 一个一个拿进来更新。（动画第 5 步）

最优解：一步一步想明白

1. 3挑子集有 2ⁿ 种，逐个算和再看是不是 11，指数级爆炸。痛点在于：很多子集只是差一个数，前面累加的和却被从头重算了一遍——同样的部分和被反复求。
2. 4为什么能用 0-1 背包？因为每个数只有「选或不选」两种，恰好对应背包里物品取一次。用一排布尔 dp[j] 记「能不能凑出和 j」：dp[0]=真（什么都不选就是 0）。每来一个数 num，从大到小扫容量更新 dp[j] = dp[j] 或 dp[j−num]——把「凑过的和记下来，不重算」。最后看 dp[11]。
3. 5容量 0~11表头是目标和 0~11，每格是「能否凑出这个和」。dp[0]=✓（凑 0 肯定行，啥都不选），其余先全 ✗。下面把 nums 里的数 1、5、11、5 一个一个拿进来更新。
4. 6dp[1] = dp[0] → ✓拿数字 1，从大到小扫容量。只有 dp[1] 能更新：它的依赖格是 dp[1−1]=dp[0]=✓，于是 dp[1] 变 ✓。现在能凑出的和是 {0, 1}。
5. 7dp[7..11] 依赖还是 ✗换数字 5，从大到小先扫到 dp[11]：它的依赖格 dp[11−5]=dp[6]现在还是 ✗，所以 dp[11] 这轮没法变真。dp[10]、dp[9]…一路往下也都因依赖格还空着保持 ✗。继续往小扫，看哪格的依赖格已经是 ✓。
6. 8dp[6] = dp[1] → ✓换数字 5，从大到小扫。先看 dp[6]：它的依赖格 dp[6−5]=dp[1]=✓，意思是「先凑出 1，再加这个 5」，所以 dp[6] 变 ✓。为什么从大到小？这样 dp[1] 还是「没用过 5」的旧值，保证这个 5 只被用一次。
7. 9dp[5] = dp[0] → ✓继续往小扫到 dp[5]：依赖格 dp[5−5]=dp[0]=✓（单独选这个 5），dp[5] 变 ✓。这个 5 处理完，能凑出的和扩到 {0, 1, 5, 6}。
8. 103 小于 5 → 装不下，沿用负例：扫到容量 3 时，3 比这个数 5 还小，5 根本装不下。这种格子直接沿用原值不动（dp[3] 还是 ✗）——代码里就是内层循环只扫到 num 为止，比 num 小的容量不碰。
9. 11dp[11] = dp[0] → ✓拿数字 11，从大到小第一个就是 dp[11]：依赖格 dp[11−11]=dp[0]=✓，相当于「单独选这个 11」就凑满了！dp[11] 变 ✓，目标已经命中。
10. 12dp[11] = ✓ → true看最后一格 dp[11]=✓：能凑出和为 11 的子集，数组可以平分，返回 true。最后那个 5 还没轮到处理就已经成功了。
11. 15「每个物品选或不选、容量恰好或不超」就是 0-1 背包。可行性用「或」、计数用「加」、最值用「max」，骨架全一样。
12. 20把这题练到能复述后，再去同类题里迁移：可行性「或」换成计数「加」就是 LC494 目标和；换成 max 装满价值就是经典 0-1 背包。状态定义复用，只改「合并」那一步。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def canPartition(self, nums):
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for x in nums:
            for s in range(target, x - 1, -1):
                dp[s] = dp[s] or dp[s - x]
        return dp[target]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0; for (int x : nums) total += x;
        if (total % 2) return false;
        int target = total / 2;
        vector<char> dp(target + 1, 0); dp[0] = 1;
        for (int x : nums)
            for (int s = target; s >= x; s--)
                if (dp[s - x]) dp[s] = 1;
        return dp[target];
    }
};

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0; for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] dp = new boolean[target + 1]; dp[0] = true;
        for (int x : nums)
            for (int s = target; s >= x; s--)
                dp[s] = dp[s] || dp[s - x];
        return dp[target];
    }
}

# 0-1 背包通用骨架：每个物品最多选一次
dp = [初值] * (W + 1)
dp[0] = 基准值
for x in items:                    # 外层枚举物品
    for j in range(W, x - 1, -1):  # 内层容量必须从大到小!
        dp[j] = 合并(dp[j], dp[j - x])  # 或 / 加 / max
return dp[W]

// 0-1 背包通用骨架：每个物品最多选一次
vector<T> dp(W + 1, 初值);
dp[0] = 基准值;
for (int x : items)               // 外层枚举物品
    for (int j = W; j >= x; j--)  // 内层容量必须从大到小!
        dp[j] = 合并(dp[j], dp[j - x]);  // 或 / 加 / max
return dp[W];

// 0-1 背包通用骨架：每个物品最多选一次
T[] dp = new T[W + 1];   // 各元素填初值
dp[0] = 基准值;
for (int x : items)               // 外层枚举物品
    for (int j = W; j >= x; j--)  // 内层容量必须从大到小!
        dp[j] = 合并(dp[j], dp[j - x]);  // 或 / 加 / max
return dp[W];

复杂度

面试官可能追问