代码随想录 416. 分割等和子集

题目

使用二维dp数组思路
首先，我们需要计算整个数组的元素和 total_sum。如果 total_sum 是奇数，那么无论如何都无法将数组分成两个和相等的子集，因此直接返回 false。
然后，我们定义一个二维布尔数组 dp，其中 dp[i][j] 表示前 i 个元素是否可以组成和为 j 的子集。
初始化 dp[0][0] 为 true，表示不选择任何元素时可以得到和为 0 的子集。对于其他的 dp[i][0]，它们也为 true，因为不选择任何元素时可以得到和为 0 的子集。
对于每个元素 nums[i]，我们遍历从 0 到 total_sum / 2 的所有可能的和 j。如果 dp[i-1][j] 为 true，说明前 i-1 个元素已经可以组成和为 j 的子集，那么第 i 个元素 nums[i] 不选择时，前 i 个元素也可以组成和为 j 的子集；如果 dp[i-1][j-nums[i]] 为 true，说明前 i-1 个元素已经可以组成和为 j-nums[i] 的子集，那么加上第 i 个元素 nums[i] 后，前 i 个元素也可以组成和为 j 的子集。
最后，如果 dp[nums.size()-1][total_sum/2] 为 true，说明前 nums.size()-1 个元素可以组成和为 total_sum/2 的子集，那么整个数组也可以分割成两个和相等的子集，返回 true；否则，返回 false。

代码实现

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total_sum = 0;
        for (int num : nums) {
            total_sum += num;
        }
        
        if (total_sum % 2 == 1) {
            return false;
        }
        
        int target_sum = total_sum / 2;
        vector<vector<bool>> dp(nums.size(), vector<bool>(target_sum + 1, false));
        
        dp[0][0] = true;
        for (int i = 1; i < nums.size(); i++) {
            dp[i][0] = true;
        }
        
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 1; j <= target_sum; j++) {
                if (j >= nums[i]) {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        return dp[nums.size()-1][target_sum];
    }
};

使用一维dp数组思路
本题可以等效为01背包问题，定义dp[j]为容量为j的背包最大价值为dp[j]. 同上思路，算出总和的一半为target，遍历建立递推公式dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);如果dp[target]=target，则说明满足条件。

代码实现

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};