vvrf / DSA.log

问题拆解

把数组分成两个和相等的子集。乍看要同时管两个集合，其实只需盯住一个：只要能挑出一个子集恰好凑出 sum / 2，剩下的元素自动构成另一半。于是题目转化为“从数组里选若干个数，能否凑出目标值 sum / 2”——每个数选或不选，恰好是 0/1 背包的判定版。

两个前置检查能提前剪掉一批用例：sum 为奇数时不可能对半分，直接返回 false；若最大元素超过 sum / 2，它放进哪一半都会超出，同样无解。

朴素做法是暴力枚举 2ⁿ 个子集，指数级不可行。背包 DP 用 dp[j] 表示“能否用前若干个数凑出和 j”，把子集枚举压成一张布尔表。

一维 0/1 背包的命门在遍历方向：j 必须从大到小。正序刷表时，dp[j - num] 可能已经是“本轮用过 num”之后的结果，再用它更新 dp[j] 就等于把同一个数装了两次。

转化为 0/1 背包

dp[j] 的转移是 dp[j] |= dp[j - num]：不选 num 时沿用旧值，选 num 时要求剩余的 j - num 在此前已经能被凑出。倒序遍历保证等号右边读到的还是“上一个数处理完”的状态。

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int x : nums) sum += x;
    if (sum % 2 == 1) return false; // 奇数不可能对半分
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true; // 什么都不选，凑出 0
    for (int num : nums) {
        for (int j = target; j >= num; j--) { // 倒序：保证每个数只用一次
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 == 1:  # 奇数不可能对半分
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True  # 什么都不选，凑出 0
    for num in nums:
        for j in range(target, num - 1, -1):  # 倒序：保证每个数只用一次
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

func canPartition(nums []int) bool {
    sum := 0
    for _, x := range nums {
        sum += x
    }
    if sum%2 == 1 { // 奇数不可能对半分
        return false
    }
    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true // 什么都不选，凑出 0
    for _, num := range nums {
        for j := target; j >= num; j-- { // 倒序：保证每个数只用一次
            dp[j] = dp[j] || dp[j-num]
        }
    }
    return dp[target]
}

pub fn can_partition(nums: Vec<i32>) -> bool {
    let sum: i32 = nums.iter().sum();
    if sum % 2 == 1 {
        return false; // 奇数不可能对半分
    }
    let target = (sum / 2) as usize;
    let mut dp = vec![false; target + 1];
    dp[0] = true; // 什么都不选，凑出 0
    for &num in &nums {
        let num = num as usize;
        for j in (num..=target).rev() { // 倒序：保证每个数只用一次
            dp[j] = dp[j] || dp[j - num];
        }
    }
    dp[target]
}

再把倒序这件事拆细一点。二维写法里转移是 dp[i][j] = dp[i-1][j] || dp[i-1][j-num]，右边全部来自上一行。压成一维后，“上一行”和“当前行”挤在同一个数组里：倒序时先更新大的 j，读 dp[j - num] 读到的仍是上一行的旧值，语义不变；一旦改成正序，小下标先被覆盖，dp[j - num] 就成了本行的新值，相当于允许重复选取——那是完全背包的转移，用在这里会把 [1, 5] 这种数组误判成能凑出 2。另一个小细节是内层循环到 j >= num 就停，更小的 j 装不下 num，只能沿用旧值，不用动。

复杂度

指标	复杂度	原因
时间	`O(n · sum/2)`	每个数刷一遍长度为 target 的表
空间	`O(sum/2)`	一维布尔数组

可以迁移的模式

“分成两组满足某种平衡”常可以固定一组的目标值，转成子集和问题；
0/1 背包压一维后倒序遍历，完全背包才正序，方向就是两者的分水岭；
先做奇偶、最大值这类可行性速判，无解的用例根本不必进 DP。

看到“从集合里挑一部分凑出某个值”，先想背包；再问一句每个元素能用几次，答案就决定了内层循环的方向。