分割等和子集：动态规划中的"打包行李"问题

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

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

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

比如：

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

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

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

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

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

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

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

第一步：判断可能性

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

1. 如果所有物品的总重量是奇数，肯定无法平均分配
2. 如果总重量是偶数，则每个箱子的目标重量 = 总重量 ÷ 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  找到了！

📝 动态规划解法

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

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

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

状态转移的推导

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

1. 不使用这个数字：dp[i][j] = dp[i-1][j]
2. 使用这个数字：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
...以此类推

💻 代码实现

class Solution {
    public boolean canPartition(int[] nums) {
        // 1. 计算总和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        // 2. 如果是奇数，直接返回false
        if (sum % 2 != 0) {
            return false;
        }
        
        // 3. 目标值就是总和的一半
        int target = sum / 2;
        
        // 4. 创建dp数组
        boolean[] dp = new boolean[target + 1];
        // 什么都不选，和为0是可能的
        dp[0] = true;
        
        // 5. 遍历每个数字
        for (int num : nums) {
            // 从大到小遍历所有可能的和
            // 为什么要从大到小？避免一个数字被使用多次！
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

🎯 举例详解代码执行过程

让我们用 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

💡 代码优化技巧

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

🎓 面试技巧

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

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

🔍 相似题目

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

🤔 思考题

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

---

作者：忍者算法
公众号：忍者算法

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

#算法面试 #LeetCode #动态规划 #背包问题