LeetCode 416. 分割等和子集

约 5 分钟
文章信息 17 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 20-50 字节跳动 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 网易 LeetCode 热题 100
标签
数组 动态规划 背包问题 0-1 背包 0-1 背包问题
目录

题目描述

✅ 416. 分割等和子集

image-20250528223343286

题意分析

给定一个只含正整数的数组，判断能否把它划分成两个子集，使两个子集的元素和相等。注意是划分，每个元素必须恰好属于其中一个子集，不能丢弃也不能重复使用，但子集内的元素不要求连续。返回值只是一个布尔量，题目并不要求给出具体的划分方案。

「两个子集和相等」这个条件可以立刻等价改写。设数组总和为 sum，若能划分，则每一份的和必然是 sum / 2。反过来，只要能从数组里选出若干个数使它们的和恰好为 sum / 2，剩下的数自然构成另一半。于是「划分成两半」被简化成了「能否选出和为某个定值的子集」，这是本题最重要的一次转化。

约束是 1 <= nums.length <= 200、1 <= nums[i] <= 100，因此 sum 最大 20000，目标值最多 10000。这个范围是一个明确的信号：解法的复杂度可以正比于「元素个数乘以目标和」，也就是伪多项式级别的 200 × 10000 = 200 万，完全跑得动。反之，枚举所有子集是 $2^{200}$，绝无可能。

边界方面，sum 为奇数时无论怎么分都不可能相等，必须直接返回 false，这一步既是剪枝也保证了后面的 sum / 2 是精确的整数除法。另外数组长度为 1 时必然无法划分，这一情形会被「奇数和」或「凑不出 target」自动覆盖，不需要单独处理。

解法：一维 0/1 背包

核心思路

两个子集和相等，等价于从数组中选出一个子集，使其和为总和的一半。因此先求总和 sum：若它是奇数，答案一定为 false；否则目标变为 target = sum / 2。

这是 0/1 背包的可行性问题。每轮开始时，dp[j] 表示只使用已经处理过的元素，能否恰好凑出和 j。初始只有 dp[0] = true，因为不选任何数可以凑出 0。

处理数字 num 时，和 j 有两种来源：不选它，保留原来的 dp[j]；选它，要求此前已经能凑出 j-num。因此转移为

dp[j] = dp[j] || dp[j-num]

容量必须从 target 倒序到 num。倒序保证 dp[j-num] 仍是处理当前数字前的旧状态，所以每个数组元素最多使用一次；若正序，同一个 num 可能在一轮内被重复使用，问题就变成完全背包。

正确性可用归纳说明：初始时 dp[0] 准确描述空集合；每轮转移完整枚举“不选当前数”和“选当前数”两种互斥情况，因此处理完所有元素后，dp[target] 当且仅当存在目标子集。剩余元素的和也为 sum-target=target，所以划分成立。

解题步骤

  • 求数组总和；若为奇数，直接返回 false。
  • 令 target = sum / 2，创建 target + 1 个布尔状态，并初始化 dp[0] = true。
  • 依次处理每个 num，令 j 从 target 递减到 num。
  • 用 dp[j] = dp[j] || dp[j-num] 合并“不选”和“选”两种情况。
  • 返回 dp[target]。

例如 [1,5,11,5] 的目标是 11，可达和集合依次从 {0} 变为 {0,1}、{0,1,5,6}，处理 11 后目标可达，最终返回 true。

代码实现

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
}

func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }

    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true

    for _, num := range nums {
        for j := target; j >= num; j-- {
            dp[j] = dp[j] || dp[j-num]
        }
    }
    return dp[target]
}

复杂度分析

  • 时间复杂度：$O(n \cdot target)$，其中 target = sum / 2。这是与数值大小相关的伪多项式复杂度。
  • 空间复杂度：$O(target)$，只保留一维可达状态。

关键点总结

  • 先把“等和划分”转换成“是否存在和为 sum/2 的子集”。
  • 这是每个元素只能选一次的 0/1 背包，可行性状态使用布尔值和逻辑或。
  • 一维 0/1 背包必须倒序枚举容量，保证转移读取的是上一轮状态。
  • dp[0] = true 是所有“选择当前数字”状态的起点。

易错点总结

  • 未判断奇数总和会出错。例如 [1,2,3,5] 的整数除法目标为 5，虽然能凑出 5，但总和 11 无法平分。
  • 容量正序更新会重复使用当前数字。例如 [2,6] 的目标为 4，正序会用同一个 2 两次并误判为 true。
  • 忘记初始化 dp[0]，所有状态都失去转移起点，例如 [1,1] 会误判。
  • 转移必须保留 dp[j] 的“不选”分支，不能直接赋值为 dp[j-num]。
  • 内层下界是 num；继续访问更小容量会产生负下标。

相似题目

题目 难度 考察点
474. 一和零 中等 背包有 0 和 1 两个容量维度，需要两层倒序循环
494. 目标和 中等 加减号问题先转化为求子集和，且要统计方案数而非可行性
879. 盈利计划 困难 人数是容量、利润是「至少」型下界维度，需对下界做截断处理
1049. 最后一块石头的重量 II 中等 求最接近一半的子集和，答案是差值最小化而不是判定是否恰好相等
698. 划分为k个相等的子集 中等 划分成 k 份而非两份，背包模型失效，要用回溯加状态压缩
LCR 101. 分割等和子集 简单 与本题同题，可用来复练倒序遍历与奇数和剪枝
LCR 102. 目标和 中等 与 494 同题，适合对照可行性背包与计数背包在转移上的差别