416 分割等和子集

一、题目

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

二、题解

方法一：二维动态规划

思路：动态规划、0-1 背包。

1. 核心思路

题目要求把数组分成两个元素和相等的子集。

假设数组中所有元素的总和为 sum，如果能够分割成两个元素和相等的子集，那么每个子集的元素和都应该是：

target = sum / 2

因此，问题可以转换为：

能否从数组中选择若干个数字，使这些数字的和恰好等于 target？

数组中的每个数字只能选择一次，因此这是一个典型的 0-1 背包问题。

首先需要判断数组总和是否为偶数：

  • 如果 sum 是奇数，就不可能平均分成两个整数和相等的子集；
  • 如果 sum 是偶数，就寻找是否存在一个和为 sum / 2 的子集。

定义：

dp[i][j]

表示：

从数组的前 i 个数字中，能否选择若干个数字，使它们的和恰好为 j。

对于当前数字 nums[i - 1]，有两种选择：

  • 不选择当前数字；
  • 选择当前数字。

只要其中一种情况可以组成和 j，那么 dp[i][j] 就是 true。

2. 具体步骤

  1. 遍历数组，计算所有元素的总和 sum。
  2. 如果 sum 是奇数，直接返回 false。
  3. 令目标值 target = sum / 2。
  4. 创建二维布尔数组 dp[n + 1][target + 1]。
  5. 初始化 dp[i][0] = true，因为不选择任何数字时，可以组成和 0。
  6. 遍历数组中的每个数字。
  7. 对于每个目标和 j：
    • 不选择当前数字时，状态为 dp[i - 1][j]；
    • 选择当前数字时，状态为 dp[i - 1][j - nums[i - 1]]。
  8. 最终返回 dp[n][target]。

3. 关键逻辑

// 不选择当前数字
dp[i][j] = dp[i - 1][j];

// 当前容量足够时，可以选择当前数字
if (j >= nums[i - 1]) {
    dp[i][j] = dp[i][j]
            || dp[i - 1][j - nums[i - 1]];
}

解释：

对于当前数字：

nums[i - 1]

有两种情况。

第一种情况：不选择当前数字。

dp[i - 1][j]

表示只使用前 i - 1 个数字时，已经可以组成和 j。

第二种情况：选择当前数字。

如果选择了当前数字 nums[i - 1]，那么还需要从前 i - 1 个数字中组成：

j - nums[i - 1]

因此对应的状态是：

dp[i - 1][j - nums[i - 1]]

所以完整的状态转移方程为：

dp[i][j] = dp[i - 1][j]
        || dp[i - 1][j - nums[i - 1]];

只要“不选择”或“选择”当前数字中的一种情况成立，dp[i][j] 就是 true。

4. 代码

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;

        // 1. 计算数组所有元素的总和
        for (int num : nums) {
            sum += num;
        }

        // 2. 总和为奇数，无法平均分成两个子集
        if (sum % 2 != 0) {
            return false;
        }

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

        /*
         * dp[i][j] 表示：
         * 从数组前 i 个数字中，能否选出若干个数字，
         * 使它们的和恰好为 j
         */
        boolean[][] dp = new boolean[n + 1][target + 1];

        // 3. 不选择任何数字时，可以组成和 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // 4. 枚举前 i 个数字
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];

            // 枚举目标和
            for (int j = 1; j <= target; j++) {
                // 不选择当前数字
                dp[i][j] = dp[i - 1][j];

                // 选择当前数字
                if (j >= num) {
                    dp[i][j] = dp[i][j]
                            || dp[i - 1][j - num];
                }
            }
        }

        // 5. 判断是否能够组成 target
        return dp[n][target];
    }
}

5. 复杂度分析

时间复杂度：O(n×target)O(n \times target)

说明：需要遍历 n 个数字，并且对于每个数字都要枚举从 1 到 target 的所有目标和。

其中：

target = sum / 2

空间复杂度：O(n×target)O(n \times target)

说明：使用了一个大小为 (n + 1) × (target + 1) 的二维动态规划数组。

方法二：一维动态规划（空间优化）

思路：0-1 背包、滚动数组、动态规划空间优化。

1. 核心思路

方法一使用二维数组：dp[i][j]

表示使用前 i 个数字能否组成和 j。

观察状态转移方程可以发现：

dp[i][j] = dp[i - 1][j]
        || dp[i - 1][j - nums[i - 1]];

第 i 行的状态只依赖第 i - 1 行，因此可以把二维数组压缩成一维数组。

定义：

dp[j]

表示：

从已经遍历过的数字中，能否选择若干个数字，使它们的和恰好为 j。

状态转移为：

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

其中：

  • 原来的 dp[j] 表示不选择当前数字；
  • dp[j - num] 表示选择当前数字。

需要特别注意：

一维数组中的目标和 j 必须从大到小倒序遍历。

这是因为每个数字只能使用一次。

如果正序遍历，当前数字更新出的状态可能会在本轮再次被使用，相当于同一个数字被选择了多次。

2. 具体步骤

  1. 计算数组所有元素的总和 sum。
  2. 如果 sum 是奇数，直接返回 false。
  3. 计算目标值 target = sum / 2。
  4. 创建一维布尔数组 dp[target + 1]。
  5. 初始化 dp[0] = true，表示不选择任何数字可以组成和 0。
  6. 遍历数组中的每个数字 num。
  7. 将目标和 j 从 target 倒序遍历到 num。
  8. 更新：
dp[j] = dp[j] || dp[j - num];
  1. 最终返回 dp[target]。

3. 关键逻辑

for (int num : nums) {
    // 必须倒序遍历，保证每个数字最多使用一次
    for (int j = target; j >= num; j--) {
        dp[j] = dp[j] || dp[j - num];
    }
}

解释：

状态转移：

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

包含两种情况。

不选择当前数字：

dp[j]

表示在没有使用当前数字时，就已经可以组成和 j。

选择当前数字：

dp[j - num]

表示之前可以组成和 j - num，现在再加入当前数字 num，就可以组成和 j。

例如，当前数字为 5，要判断能否组成和 11：

11 - 5 = 6

如果之前可以组成和 6，那么再选择当前数字 5，就可以组成和 11。

所以：

dp[11] = dp[11] || dp[6];

目标和必须倒序遍历。

假设当前数字是 2，如果正序遍历：

dp[2] = dp[0]  → true
dp[4] = dp[2]  → true

更新 dp[4] 时使用了本轮刚刚更新的 dp[2]，相当于数字 2 被使用了两次。

而倒序遍历时，dp[j - num] 保存的仍然是上一轮的状态，可以保证当前数字只使用一次。

4. 代码

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;

        // 1. 计算数组所有元素的总和
        for (int num : nums) {
            sum += num;
        }

        // 2. 总和为奇数，无法平均分成两个子集
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;

        /*
         * dp[j] 表示：
         * 从已经遍历过的数字中，能否选出若干个数字，
         * 使它们的和恰好为 j
         */
        boolean[] dp = new boolean[target + 1];

        // 3. 不选择任何数字时，可以组成和 0
        dp[0] = true;

        // 4. 遍历数组中的每个数字
        for (int num : nums) {
            /*
             * 必须倒序遍历：
             * 保证每个数字最多只能使用一次
             */
            for (int j = target; j >= num; j--) {
                // 不选择当前数字，或者选择当前数字
                dp[j] = dp[j] || dp[j - num];
            }

            // 已经能够组成 target，可以提前返回
            if (dp[target]) {
                return true;
            }
        }

        // 5. 判断是否能够组成 target
        return dp[target];
    }
}

5. 复杂度分析

时间复杂度：O(n×target)O(n \times target)

说明：需要遍历 n 个数字，每个数字最多枚举 target 个状态。

空间复杂度：O(target)O(target)

说明：只使用了一个长度为 target + 1 的一维动态规划数组。

评论