[代码随机化日 34] 动态编程 Part03-416.等分与子集

题目链接/文章讲解：代码随想录
视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili

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;
        int n = nums.length;

        // 创建一个 dp 数组，表示是否可以达到特定的和
        boolean[][] dp = new boolean[n + 1][target + 1];

        // 初始化：可以达到和为 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // 填充 dp 数组
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                if (j < nums[i - 1]) {
                    // 当前数字大于目标和，无法选择它
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选择当前数字或不选择它
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        // 返回能否达到 target
        return dp[n][target];
    }
}

代码解释

1. 计算总和: 首先通过一个循环计算 nums 数组的总和 sum。

2. 检查奇偶性: 如果 sum 是奇数，则不可能将数组分成两个相等的子集，直接返回 false。

3. 动态规划数组: 创建一个二维布尔数组 dp，其中 dp[i][j] 表示前 i 个数字是否可以组成和为 j 的子集。

4. 初始化:

   • 任何情况下，和为 0 只需要不选择任何数字，因此 dp[i][0] 都是 true。

5. 填充 dp 数组:

   • 通过两层循环遍历每个数字和每个可能的和。如果当前数字大于目标和 j，则无法选择它，dp[i][j] 等于不选择它的结果 dp[i-1][j]。
   • 如果可以选择当前数字，则 dp[i][j] 等于选择当前数字或不选择它的结果，即 dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i - 1]]。

6. 返回结果: 最后返回 dp[n][target]，表示是否可以用前 n 个数字组成和为 target 的子集。