分割等和子集 图解题解

分割等和子集为什么等价于凑出总和的一半

题目给一个正整数数组 nums，问能不能把它分成两个子集，让两边元素和相等。直接想「怎么分两堆」会很乱，先做一步翻译：两个子集和相等，每一份必然恰好是总和 sum 的一半；反过来，只要能挑出一些数凑出 sum/2，剩下的数自动构成另一半。于是问题变成判定题：能否选出和恰好等于 sum/2 的子集。

这一步还送一个提前剪枝：sum 是奇数时一半不是整数，正整数无论怎么选都凑不出，直接返回 false。以 nums=[1,2,3,4] 为例，sum=10、目标是 5，{1,4} 和 {2,3} 各凑 5，答案为 true。

为什么这是一个 0-1 背包问题

「从 n 个数里挑一些、每个至多用一次、凑出目标和」正是 0-1 背包的判定版：每个数是一件物品，体积就是数值本身，容量是 sum/2，只关心能不能装满。暴力枚举所有子集是 2 的 n 次方种，指数爆炸。

关键观察是：面对一个新的数 x，任何一种凑法要么用了 x、要么没用。没用时，能凑出哪些和与之前完全一样；用了时，能凑出 w 当且仅当之前能凑出 w - x。「前若干个数能凑出哪些和」这一份信息，足以推出加入下一个数后的全部答案，不必记住具体选了谁——这就是动态规划能压缩指数级搜索的原因。

dp 数组怎么定义，dp[0] 为什么必须是 true

定义布尔数组 dp，dp[w] 表示：用目前已考虑过的数，能否凑出和恰好为 w。初始只有 dp[0]=true——空集的和就是 0，其余全是 false。每加入一个数 x，转移是 dp[w] = dp[w] or dp[w - x]：前者对应不选 x，后者对应选 x、看之前能否凑出 w - x。

dp[0]=true 绝不能漏，它是所有递推的种子：一个数 x 能单独凑出 x，正是靠 dp[x - x] = dp[0] 传导出来的。写成 false，整张表永远推不出任何 true。

一维数组为什么必须倒序更新容量

用一维数组滚动时，内层循环必须让容量 w 从大到小（从 target 减到 x）。原因在于：算 dp[w] 时引用的 dp[w - x] 必须是还没被当前这个数更新过的旧值，代表「不含 x 的历史状态」；倒序扫描时小容量还没被碰过，引用到的正是旧值。

如果正序更新，dp[w - x] 可能已被本轮的 x 更新过，再拿它推 dp[w] 等于把同一个数用了两次——那是完全背包的语义，会把「凑不出」误判成「凑得出」。倒序这一个方向，就是「每个数只能用一次」在代码里的全部体现。

复杂度怎么算，哪些边界容易翻车

时间复杂度 O(n·target)：n 个数，每个数把容量从 target 到自身扫一遍，target 是总和的一半。空间 O(target)，一维布尔数组即可。这是和数值大小挂钩的伪多项式复杂度。

三个高频翻车点：忘了先判总和奇偶；一维数组正序更新，悄悄变成完全背包；漏掉 dp[0]=true 这个空集起点。另外题目保证正整数，若元素可能为负，容量非负的背包框架不再适用，需改用可达和集合等写法。

Python

def canPartition(nums):
    s = sum(nums)
    if s % 2: return False
    t = s // 2
    dp = [True] + [False] * t
    for x in nums:
        for w in range(t, x - 1, -1):
            dp[w] = dp[w] or dp[w - x]
    return dp[t]

C++

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

Java

boolean canPartition(int[] nums){
    int s = 0; for(int x : nums) s += x;
    if(s % 2 == 1) return false;
    int t = s / 2;
    boolean[] dp = new boolean[t + 1]; dp[0] = true;
    for(int x : nums)
        for(int w = t; w >= x; w--)
            dp[w] = dp[w] || dp[w - x];
    return dp[t];
}