LeetCode 热题 100_分割等和子集（89_416_中等_C++）(动态规划)

题目描述：

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

题解：

解题思路：

思路一（动态规划）：

1、是否可以分割成两部分的和，可以先求出数组中元素的总和(sum)。若总和为偶数则可能分割成两部分，若为奇数则不能分割成两部分（数组中的元素为偶数）。若为偶数，则需要考察部分数组元素的和是否等于sum/2。若存在则可分割，若不存在则不可分割。
我们发现，部分元素的和是否等于sum/2，也就是01背包类型的问题(背包容量为sum/2,物品的重量 = 物品的价值（nums[i]）)

• dp[ j ] 代表容量为 j 时能放的最大价值为 dp[ j ]。
• 从而推出递推公式 dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
• 因上述递推公式取 max 且 容量为 0 时能放的最大价值为 0 所以 dp 数组初始化为 0。
• 当 dp[ sum/2 ] = sum/2 时背包可以装满返回 true，否则返回false。

2、复杂度分析：
① 时间复杂度：O(n * sum)，其中 n 是数组大小，sum 是数组元素的总和。
② 空间复杂度：O(sum)，其中 sum 是数组元素的总和，dp数组消耗的空间。

代码实现

代码实现（思路一（动态规划））：

class Solution {
public:
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        // 计算所有数字的总和
        for (const auto &num : nums) {
            sum += num;
        }

        // 如果总和是奇数，无法将数组分成两个和相等的部分
        // 使用位运算 sum & 1 判断是否为奇数
        if (sum & 1) {
            return false;  // 如果是奇数，直接返回 false
        }

        // 目标是将数组分成两部分，每部分的和为 sum / 2
        // 由于 sum 是偶数，sum / 2 就是目标和(注意右移的位数)
        int capacity = sum >> 1;  // 相当于 sum / 2，使用位运算提高效率
        vector<int> dp(capacity + 1, 0);  // dp 数组，大小为 capacity + 1，初始化为 0

        // 遍历数组中的每个数字
        for (int i = 0; i < nums.size(); ++i) {
            // 从容量 capacity 往下遍历，避免重复使用同一个数字
            // 如果 j >= nums[i]，我们可以选择将 nums[i] 加入到组合中
            for (int j = capacity; j >= nums[i]; --j) {
                // 更新 dp[j]，表示是否能达到和为 j
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        // 最后，检查 dp[capacity] 是否等于 capacity
        // 如果 dp[capacity] 等于 capacity，表示可以分割成两部分和相等
        if (dp[capacity] == capacity) {
            return true;  // 可以分割，返回 true
        }

        return false;  // 不能分割，返回 false
    }
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        // 计算所有数字的总和
        for (const auto &num : nums) {
            sum += num;
        }

        // 如果总和是奇数，无法将数组分成两个和相等的部分
        // 使用位运算 sum & 1 判断是否为奇数
        if (sum & 1) {
            return false;  // 如果是奇数，直接返回 false
        }

        // 目标是将数组分成两部分，每部分的和为 sum / 2
        // 由于 sum 是偶数，sum / 2 就是目标和(注意右移的位数)
        int capacity = sum >> 1;  // 相当于 sum / 2，使用位运算提高效率
        vector<int> dp(capacity + 1, 0);  // dp 数组，大小为 capacity + 1，初始化为 0

        // 遍历数组中的每个数字
        for (int i = 0; i < nums.size(); ++i) {
            // 从容量 capacity 往下遍历，避免重复使用同一个数字
            // 如果 j >= nums[i]，我们可以选择将 nums[i] 加入到组合中
            for (int j = capacity; j >= nums[i]; --j) {
                // 更新 dp[j]，表示是否能达到和为 j
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        // 最后，检查 dp[capacity] 是否等于 capacity
        // 如果 dp[capacity] 等于 capacity，表示可以分割成两部分和相等
        if (dp[capacity] == capacity) {
            return true;  // 可以分割，返回 true
        }

        return false;  // 不能分割，返回 false
    }
};

int main(int argc, char const *argv[])
{
    vector<int> nums={1,2,5};
    Solution s;
    if(s.canPartition(nums)){
        cout<<"true";
    }else{
        cout<<"false";
    }
    return 0;
}

LeetCode 热题 100_分割等和子集（89_416)原题链接
欢迎大家和我沟通交流(✿◠‿◠)