LeetCode 416. 分割等和子集

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

题目描述

✅ 416. 分割等和子集

image-20260928200714793

题意分析

给定一个只包含正整数的数组，判断能否把全部元素分到两个子集中，使两边元素和相等。每个数组位置只能属于其中一组，不要求两组元素数量相同，也不要求组内元素在原数组中连续。

设总和为 sum，两组都必须等于 sum / 2。如果总和为奇数就无法平分；如果为偶数，只要找到一个和恰好为一半的子集，剩下的所有元素自然组成另一半。相同数值出现在不同位置时，仍是可以分别选择的元素。

解法：一维 0/1 背包

核心思路

[!blue]

将目标设为 target = sum / 2，问题就变成从数组中选出若干元素，能否恰好凑出目标和。每个位置最多选一次，这是 0/1 背包；这里只判断可行性，因此使用布尔状态。

定义 dp[j] 表示使用已经处理过的元素，能否凑出和 j。初始尚未处理任何元素，只有空集合能凑出零，所以 dp[0] = true，其他状态为假。

处理当前元素 num 时，对和 j 有两种选择：不选它，保留原来的 dp[j]；选它，就要求之前的元素能凑出 j - num。两者任意成立都可行，因此更新为 dp[j] = dp[j] || dp[j - num]。

两个来源本来都应属于处理当前元素之前的状态。压缩成一维数组后，必须从大到小更新 j：因为 num 为正，j - num < j，较小位置还未在本轮改写，读取到的正是旧状态。如果从小到大更新，就可能把本轮刚使用 num 的结果再次拿来转移，导致同一个数组位置被重复使用。

只维护 0 到 target 的和即可。所有元素都是正数，超过目标后不可能再通过加入其他元素降回目标；当 num > target 时，当前内层循环自然跳过。处理完所有元素后，dp[target] 就是能否完成等和划分的答案。

解题步骤

  1. 求数组总和；若为奇数，直接返回 false。
  2. 令 target = sum / 2，分配 target + 1 个布尔状态，初始化 dp[0] = true。
  3. 依次处理每个元素 num，让 j 从 target 递减到 num。
  4. 使用 dp[j] = dp[j] || dp[j - num] 合并不选和选择当前元素两种情况。
  5. 返回 dp[target]。

代码实现

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)$，其中 n 为元素个数，target = sum / 2。每个元素最多检查全部目标容量；复杂度依赖数值总和，而不只是数组长度。
  • 空间复杂度：$O(target)$，仅保存各个和是否可达的一维数组。

关键点总结

[!green]

  • 找到一半和的子集即可，补集会自动凑成另一半，不需要同时维护两组。
  • 不同位置的相同值可以分别使用，但同一位置不能重复使用，倒序更新负责保证这一点。
  • 状态表示恰好可达的和，而不是不超过容量的最大收益，因此使用布尔值和逻辑或。

易错点总结

[!yellow]

  • 总和为奇数时直接整除得到目标，会把两个和不相等的子集误判成等和划分，必须先判断奇偶。
  • 容量从小到大更新，会允许当前元素在同一轮反复参与转移，把 0/1 选择变成可重复选择。
  • 忘记初始化 dp[0]，所有选择分支都缺少起点，无法形成任何正数和。
  • 直接赋值为 dp[j - num] 会丢掉不选当前元素的方案，必须保留旧 dp[j]。
  • 内层下界是 num，只有 j >= num 时才能访问 j - num，否则会产生负下标。

相似题目

题目 难度 关联与区别
494. 目标和 中等 都能转成0/1子集和，本题只判断能否取到总和一半，原题统计赋号方案数。
1049. 最后一块石头的重量 II 中等 同样把元素分成两组，原题最小化两组和之差，本题要求差恰为0。
474. 一和零 中等 用容量动态规划表示可达和或组合数；本题判断能否达到总和的一半，该题把容量扩展为零和一的两维预算。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63371951
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！