算法训练营第一期 | 分割等和子集

一、题目描述

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

二、题目解析

三、参考代码

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

        // 使用 sum 来保存数组中全部元素的和
        int sum = 0;

        // 遍历 nums 数组
        for (int i = 0 ; i < nums.length ; i++){
            // 把 nums 数组上的所有元素值累加到 sum 上
            sum += nums[i];
        }

        // 如果发现 sum 为奇数,那么必然无法拆分为两个相等的整数
        if(sum % 2 == 1){
            // 所以无法将这个数组分割成两个子集,返回false
            return false;
        }

        // 获取数组的长度
        int n = nums.length;

        // 获取数组中全部元素之后的一半
        // 接下来需要在数组 nums 中寻找一些数字去拼凑为 target
        // 如果能找到一些数字之和为 target,那么剩下的数字之和也是 target
        int target = sum / 2;

        // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
        // dp[0][0] 表示 nums 的前 0 个元素能否可以组成和为 0 的结果
        // dp[2][6] 表示 nums 的前 2 个元素能否可以组成和为 6 的结果
        // dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        // i 的值从 0 到 n - 1
        // j 的值从 0 到 target
        boolean[][] dp = new boolean[n][target + 1];

        // 先初始化  dp[0][nums[0]]
        // 如果 nums 的第 0 个元素 nums[0] 小于 target
        if (nums[0] <= target) {
            // 那么 nums 的前 0 个元素能否可以组成和为 nums[0] 的结果是 true
            // 因为 nums 的前 0 个元素就是 nums[0]
            dp[0][nums[0]] = true;
        }


        // 接下来开始往 dp 数组中填充结果
        // i 的值从 1 到 n - 1
        for (int i = 1; i < n; i++) {
            // j 的值从 0 到 target
            for (int j = 0; j <= target; j++) {
                // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                // dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                // 对于 dp[i][j] 来说,如果 dp[i - 1][j] 为 true,那么 dp[i][j] 必然也为 true
                // 所以,先初始化 dp[i][j] 的值为 dp[i - 1][j] 的值
                // 再通过后面的代码修改 dp[i][j] 中还为 false 的值 
                dp[i][j] = dp[i - 1][j];

                // 如果此时 nums[i] 恰巧为 j
                // 那么对于 dp[i][j] 来说,nums 的前 i 个元素可以组成和为 j 的结果
                if (nums[i] == j) {
                    // 所以 dp[i][j] 为 true
                    dp[i][j] = true;
                    // 同时继续
                    continue;
                }

                // 如果发现 nums[i] 小于 j
                if (nums[i] < j) {
                    // dp[i][j] 表示 nums 的前 i 个元素能否可以组成和为 j 的结果
                    // dp[i - 1][j] 表示 nums 的前 i - 1 个元素能否可以组成和为 j 的结果
                    // dp[i - 1][j - nums[i]] 表示 nums 的前 i - 1 个元素能否可以组成和为 j - nums[i] 的结果
                    // 那么 dp[i][j] 的结果要为 true
                    // 1、nums 的前 i - 1 个元素可以组成和为 j 
                    // 2、nums 的前 i - 1 个元素可以组成和为 j - nums[i]
                    // 对于 1 来说,不用使用 nums[i] 就组成了 j
                    // 对于 2 来说,前 i - 1 个元素可以组成和为 j - nums[i],那么加上此时的值 nums[i],也组成了 j
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }

        // dp[n - 1][target ] 表示 nums 的前 n - 1 个元素能否可以组成和为 target 的结果
        // 返回这个结果
        return dp[n - 1][target];

    }
}

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注