416. 分割等和子集#

大家好！今天我们来聊一道非常有意思的题目，它让我想起了收拾行李时要平均分配重量的场景。这道题就是”分割等和子集”，虽然是动态规划题目，但我保证用生活中的例子，让你轻松理解它的精髓。

🎯 问题描述：行李分配问题#

给你一个只包含正整数的数组 nums，问是否可以将这个数组分成两个子集，使得两个子集的元素和相等。

比如：

输入：nums = [1,5,11,5]
输出：true
解释：可以分成 [1,5,5] 和 [11]，它们的和都是 11

输入：nums = [1,2,3,5]
输出：false
解释：无法分成两个和相等的子集

plaintext

问题描述#

题目目标#

给定一个只包含正整数的非空数组 nums ，请判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1#

输入： nums = [1,5,11,5] 输出： true 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

🤔 让我们用生活场景来理解#

想象你和朋友要去旅行，有几件物品需要分配到两个箱子里，要求两个箱子重量相同。

比如有这些物品：1kg的水、5kg的衣服、11kg的鞋子、5kg的书

能否将它们分成重量相等的两份？
如果可以，怎么分？

💡 解题思路：从生活场景到算法#

第一步：判断可能性#

首先，我们要知道分配是否有可能成功：

如果所有物品的总重量是奇数，肯定无法平均分配
如果总重量是偶数，则每个箱子的目标重量 = 总重量 ÷ 2

例如：[1,5,11,5]

总重量 = 22kg
目标重量 = 11kg

第二步：转化为背包问题#

仔细想想，这不就变成了：

能否从这些物品中挑选一些，使得总重量正好等于 11kg？

这就是经典的 0-1 背包问题！

第三步：用具体例子理解#

拿 nums = [1,5,11,5] 来说：

目标：找出和为11的子集

尝试过程：
[1]       → 和=1
[1,5]     → 和=6
[1,5,5]   → 和=11  找到了！

plaintext

📝 动态规划解法#

理解了问题的本质，我们来设计动态规划解法：

dp[i][j] 表示：使用前i个数字，能否组成和为j的子集

例如：dp[3][6] = true 表示：使用前3个数字，可以组成和为6的子集

状态转移的推导#

对于每个数字，我们有两个选择：

不使用这个数字：dp[i][j] = dp[i-1][j]
使用这个数字：dp[i][j] = dp[i-1][j-nums[i]]

让我们用例子来看：

nums = [1,5,11,5], target = 11

第一步：只有数字1
dp[1][1] = true  (使用1)
dp[1][2~11] = false

第二步：加入数字5
dp[2][1] = true   (来自dp[1][1])
dp[2][5] = true   (直接使用5)
dp[2][6] = true   (1+5)

第三步：加入数字11
...以此类推

plaintext

💻 代码实现#

class Solution {
    public boolean canPartition(int[] nums) {
        // 1) 计算数组元素总和，用于判断是否可能平分
        int sum = 0;
        for (int num : nums) {
            // 累加每个元素到总和
            sum += num;
        }

        // 2) 若总和为奇数，不可能分成两个相等整数和的子集
        if (sum % 2 != 0) {
            return false;
        }

        // 3) 目标子集和：只需判断能否选出若干数凑成 sum/2
        int target = sum / 2;

        // 4) 一维 0-1 背包：dp[j] 表示“是否能凑出和 j”
        boolean[] dp = new boolean[target + 1];
        // 基础状态：不选任何数时，可以凑出和 0
        dp[0] = true;

        // 5) 逐个处理每个数字，每个数字只能用一次（0-1 背包）
        for (int num : nums) {
            // 从大到小遍历所有可能的和
            // 为什么要从大到小？避免一个数字被使用多次！
            for (int j = target; j >= num; j--) {
                // 转移：当前和 j 可达，当且仅当
                // - 之前就可达 dp[j] 为 true，或
                // - 去掉当前 num 后的和 j-num 可达 dp[j-num] 为 true
                dp[j] = dp[j] || dp[j - num];
            }
        }

        // 最终判断 target 是否可达，可达则能平分
        return dp[target];
    }
}

java

🎯 举例详解代码执行过程#

让我们用 nums = [1,5,11,5] 来看代码是如何工作的：

初始状态：
dp[0] = true，其他都是false

处理数字1：
dp[1] = dp[0] = true
dp[2~11] 保持false

处理数字5：
dp[5] = dp[0] = true
dp[6] = dp[1] = true

处理数字11：
dp[11] = dp[0] = true
dp[12] = dp[1] = true
...

最后检查 dp[11] 是否为true

plaintext

💡 代码优化技巧#

使用一维数组而不是二维数组，节省空间
可以提前判断：如果最大数字超过sum/2，直接返回false
从大到小遍历避免重复使用同一个数字

🎓 面试技巧#

遇到这题时，建议这样展开思路：

先说明问题的本质：寻找和为sum/2的子集
用生活例子解释问题（比如行李分配）
说明如何转化为0-1背包问题
最后展开动态规划解法

🔍 相似题目#

0-1背包问题
目标和（Target Sum）
最后一块石头的重量 II

🤔 思考题#

如果要求打印出具体的分配方案，该如何修改代码？

动态规划有时看起来很抽象，但很多时候它解决的都是现实生活中的问题。希望通过行李分配这个场景，能帮助你更好地理解这道题！