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
思路:
这个问题可以通过动态规划来解决,本质上是一个“0-1 背包问题”。
我们可以将问题转化为:是否能从数组 nums
中选出一些数,使得它们的和等于整个数组总和的一半。
具体思路:
-
计算总和:首先计算数组
nums
的总和sum
,如果sum
是奇数,那么不可能将数组分成两个和相等的子集,直接返回false
。 -
目标值:将目标值设为
target = sum / 2
,问题就转化为在nums
中是否存在一个子集,它们的和恰好等于target
。 -
定义 DP 数组:
- 定义一个布尔型动态规划数组
dp
,其中dp[i]
表示是否存在和为i
的子集。 - 初始化
dp[0] = true
,因为和为 0 的子集是空集,总是可以实现的。
- 定义一个布尔型动态规划数组
-
状态转移:
- 对于每个数
num
,从后往前遍历dp
数组,如果dp[j - num]
为true
,则设置dp[j] = true
,表示可以通过当前的数num
实现和为j
的子集。
- 对于每个数
-
结果:
- 最后查看
dp[target]
是否为true
,如果是则表示存在子集的和等于target
,返回true
;否则返回false
。
- 最后查看
上代码:
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 != 0) return false; // 如果总和为奇数,直接返回 falseint target = sum / 2;vector<bool> dp(target + 1, false);dp[0] = true; // 和为 0 的子集总是存在的for (int num : nums) {for (int j = target; j >= num; --j) {dp[j] = dp[j] || dp[j - num];}}return dp[target];}
};