LeetCode 热题 100_分割等和子集（89_416）
- 题目描述：
- 输入输出样例：
- 题解：
- 解题思路：
- 思路一（动态规划）：
- 代码实现
- 代码实现（思路一（动态规划））：
- 以思路一为例进行调试
题目描述：
给你一个 只包含正整数 的 非空 数组 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]，表示是否能达到和为 jdp[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]，表示是否能达到和为 jdp[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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
