【力扣】[热题HOT100]416. 分割等和子集

1、题目

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

链接:https://leetcode-cn.com/problems/partition-equal-subset-sum/

2、思路分析

1)动态规划
题目理解:一个非空正整数的数组nums, 从数组中挑出一些数字,是否可以等于数组中所有数字的总和的一半,这个问题可以转换成 0-1 背包问题。

健壮性:数组中总和为奇数的必定返回false;数组中的数字小于2的也返回false;数组中最大的数字超过数组和的一半返回false。

创建二维数组dp,n 行 target + 1 列,dp[i][j] 表示从数组的 [0,i]下标范围内选取若干个正整数,是否存在一种选取方案使得被选取的正整数的和等于 j 。dp初始化全部为false。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int max = *max_element(nums.begin(), nums.end()); // 剔除最大数大于平均数的情况
        if(sum & 1)
        {
            return false;  // 和为奇数找不到
        }

        int target = sum / 2;
        if(max > target){
            return false;
        }

        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        for(int i = 0; i < n; ++i){
            dp[i][0] = true;
        }

        dp[0][nums[0]] = true;

        for(int i = 1; i < n; ++i)
        {
            int num = nums[i];
            for(int j = 1; j <= target; ++j)
            {
                if(j >= num)
                {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
};

2)动态规划优化(降低空间复杂度)
上述代码的空间复杂度是 O(n×target)。但是可以发现在计算dp 的过程中,每一行的 dp 值都只与上一行的 dpdp 值有关,因此只需要一个一维数组即可将空间复杂度降到 O(target)。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int max = *max_element(nums.begin(), nums.end()); // 剔除最大数大于平均数的情况
        if(sum & 1)
        {
            return false;  // 和为奇数找不到
        }

        int target = sum / 2;
        if(max > target){
            return false;
        }

        vector<int> dp(target + 1, 0);
        dp[0] = true;
        for(int i = 0; i < n; ++i)
        {
            int num = nums[i];
            for(int j = target; j >= num; --j)
            {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
};
上一篇:416.分割等和子集。01背包


下一篇:416. 分割等和子集