LC416.分割等和子集

题目描述

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

题目解析

好的，没问题！我是 AlgoMooc 的算法老师，今天我们来一起攻克这道看似有点吓人，但其实非常经典的题目——分割等和子集。

别担心，我会用最通俗的方式，带你一步步把它搞懂。

---

题目在说什么

简单来说，就是给你一堆正整数（比如 [1, 5, 11, 5]），问你能不能把这堆数分成两堆，使得这两堆数的总和相等。

举个生活中的例子：

你和你的朋友分糖果，总共有 4 堆糖果，数量分别是 1、5、11、5 颗。你们想公平地分，每人拿到的糖果总数要一样多。那么问题就是：能不能找到一种分法，让两人手里的糖果总数相等？

在这个例子里，答案是“能”。因为 1 + 5 + 5 = 11，另一堆就是单独的 11，两堆总和都是 11，完美平分。

如果总糖果数是奇数，比如总和是 23，那肯定没法分成两个相等的整数，因为 23 除以 2 不是整数。所以，第一步就是看总和是不是偶数。

---

思路是怎么来的

这道题其实是一个“伪装”起来的 0-1 背包问题。

什么是 0-1 背包问题？

想象你有一个背包，容量是固定的。面前有 n 个物品，每个物品有自己的重量和价值。你要决定每个物品是“装进背包（选）”还是“不装（不选）”，目标是让背包里的总价值最大。

我们的问题跟它很像，但目标不同：

• 背包容量：变成了“目标和”，也就是总和的一半（target）。
• 物品：就是数组里的每个数字。
• 目标：不是求最大价值，而是问“能不能刚好把背包塞满，不多不少，正好等于 target”。

所以，我们的问题就变成了：从数组中挑选一些数字（每个数字只能选一次，就像 0-1 背包里的物品），看看能不能让它们的和正好等于 target。

这个思路是怎么想到的呢？

1. 先算总和：我们先把所有数字加起来，得到总和 sum。 2. 判断奇偶：如果 sum 是奇数，直接说“不行”，因为两个相等的整数加起来不可能是奇数。 3. 确定目标：如果 sum 是偶数，那么目标 target = sum / 2。现在问题就变成了：能不能从数组里挑出一些数，让它们的和等于 target？如果能，剩下的数自然也就等于 target 了。

你看，这样一转化，问题就清晰多了。

---

代码逐步拆解

现在，我们来看参考代码，我会把每一行都解释清楚。

class Solution {
    public boolean canPartition(int[] nums) {

        // 1. 计算总和
        int sum = 0;
        for (int i = 0 ; i < nums.length ; i++){
            sum += nums[i];
        }

        // 2. 如果总和是奇数，直接返回 false
        if(sum % 2 == 1){
            return false;
        }

        int n = nums.length;
        int target = sum / 2;

        // 3. 创建 DP 表格
        // dp[i][j] 的意思是：考虑数组的前 i 个元素（下标从 0 到 i-1），
        // 能不能选出一些数，使它们的和恰好为 j。
        // 注意：这里 i 从 0 到 n-1，j 从 0 到 target。
        boolean[][] dp = new boolean[n][target + 1];

        // 4. 初始化第一行（只考虑第一个元素 nums[0]）
        // 如果 nums[0] 本身就等于 target，那当然可以。
        // 但更常见的是，nums[0] 小于 target，那么 dp[0][nums[0]] 就是 true。
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        // 5. 填充 DP 表格
        // 从 i = 1 开始，因为第 0 行已经初始化了
        for (int i = 1; i < n; i++) {
            // 对于每个可能的和 j
            for (int j = 0; j <= target; j++) {
                // 情况一：不选当前数字 nums[i]
                // 如果前 i-1 个元素就能组成和 j，那么加上当前元素不选，自然也能组成。
                dp[i][j] = dp[i - 1][j];

                // 情况二：选当前数字 nums[i]
                // 如果 nums[i] 正好等于 j，那当然可以
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue; // 已经确定了，不用再看下面的情况了
                }

                // 如果 nums[i] 小于 j，那么我们需要看看：
                // 前 i-1 个元素能不能组成和 (j - nums[i])。
                // 如果能，那么加上 nums[i] 就能组成 j。
                if (nums[i] < j) {
                    // dp[i - 1][j - nums[i]] 就是看前 i-1 个元素能不能组成 (j - nums[i])
                    // 只要有一个为 true，dp[i][j] 就是 true
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];
                }