59 分割等和子集

给你一个只包含正整数的非空数组 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

NP 完全问题（01背包）

特点是：「每个数只能用一次」。解决的基本思路是：物品一个一个选，容量也一点一点增加去考虑，这一点是「动态规划」的思想

对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」:

1. 不选择 nums[i]，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
2. 选择 nums[i]，如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
3. 状态转移方程为 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]

注意：观察状态转移方程，or 的结果只要为真，表格 这一列 下面所有的值都为真。

因此在填表的时候，只要表格的最后一列是 true，代码就可以结束，直接返回 true。（题解2）

题解1 二维DP

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = nums.size();
        int sumN = 0;
        
        for(auto&k : nums) sumN += k;
        // 总和不是偶数就不能分割成2 parts了
        if(sumN % 2) return false;
        
        sumN = sumN >> 1;
        // dp[i][j]: 从[0,i]范围内选取若干个正整数（可以是0个），是否存在一种选取方案使得被选取的正整数的和（物品重量总和）等于j（背包容量）
        // 如果dp.row = s,则需要设定dp[0][nums[0]]=true;后面的代码逻辑可以保持一致（有i-1）
        vector<vector<bool>> dp(s+1, vector<bool>(sumN+1, false));
        // 背包容量为0时 不放入就满足条件    
        for(int i = 1; i < s; i++){
            dp[i][0] = true;
        }

        for(int i = 1; i <= s; i++){
            for(int j = 1; j <= sumN; 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]];
            }
        }       
        return dp[s][sumN];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

题解2 空间优化DP（改为1D）

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = nums.size();
        int sumN = 0, maxN = 0;
        
        for(auto&k : nums){
            sumN += k;
            maxN = max(maxN, k);
        }
        if(sumN % 2) return false;
        
        sumN = sumN >> 1;
        // 剪枝
        if(maxN > sumN) return false;

        vector<bool> dp(sumN+1, false);
        dp[0] = true;

        for(int i = 0; i < s; i++){
        // 这里注意从大到小计算（保证是前行的意思）
            for(int j = sumN; j >= nums[i]; j--){
            // 启发自dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];（只与上一行的值有关）
                dp[j] = dp[j] || dp[j-nums[i]];
            }
            // （可能会加速）
            if(dp[sumN]) return true;
        }
        return dp[sumN];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31