LeetCode416. 分割等和子集（2024冬季每日一题 31）

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

$1<=nums.length<=200$
$1<=nums[i]<=100$

思路：动态规划

• 找两个子集，使得两个子集的和相等，相当于找，在 [0, n-1] 取元素，每个元素最多取一次，使得取到的元素和恰好 = 总和的一半（sum/2）
• 所以题目就转换成了，在 [0, n-1] 取元素，使得和恰好等于 sum/2
• 可以看出类似于 0/1 背包问题，和 0/1 背包的区别在于
• 一个是不超过 背包容量，一个是恰好等于 背包容量
• 一个是求 max 最大值，一个是求是否存在 bool 值
• 所以类别 0/1 背包，可以定义当前动态规划 问题
• f[i][j]：在[0…i] 中取元素，每个元素最多取一次，是否和恰好能凑够 j
• 状态转移方程：
  • 如果当前下标为 i 的元素，nums[i] > j，则肯定不能取当前元素，所以 f[i][j] = f[i-1][j]（即去掉当前第 i 个元素，在 [0…i-1] 中取元素，是否恰好凑够 j）
  • 如果 nums[i] <= j，则可以取当前元素/不取当前元素，f[i][j] = f[i-1][j-nums[i]] | f[i-1][j]，即不取当前元素的话，同上，取当前元素的话，是否能凑够 j，则需要判断，去掉当前元素在 [0…i-1] 中取，是否恰好能凑够 j - nums[i]
• 注意：
  • 对于 f[i][0]，即从 [0…i] 中取，恰好能凑够 0 的位置，一定是 true，因为凑 0 不需要去任何元素即可
  • f[0][nums[0]] = true，即只有第一个元素时，只能凑够 j = nums[0]（这里这样特判，是因为后面遍历的时候可以 i 从 1 开始，状态转移方程中 f[i-1][x]，其中的 i - 1 就不用特殊判断了）

class Solution {
public:
    // 从前i个物品中选，总和恰好等于j的集合
    // 是否能恰好凑够 j
    bool f[210][20010];
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return false;
        int sum = 0, mN = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];
            mN = max(mN, nums[i]);
        }
        if(sum % 2) return false;
        sum /= 2;
        if(mN > sum) return false;
        for(int i = 0; i < n; i++)
            f[i][0] = true;
        f[0][nums[0]] = true;
        for(int i = 1; i < n; i++){
            for(int j = 1; j <= sum; j++){
                f[i][j] = f[i-1][j];
                if(nums[i] <= j) f[i][j] = f[i][j] | f[i-1][j-nums[i]];
            }
        }
        return f[n-1][sum];
    }
};