[数据结构与算法]【力扣】[热题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];
    }
};