题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 给你一个只包含正整数的非空数组 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、今天进入 np 的背包的问题，np背包问题只有 0 或 1；两种返回值，本题为求数组等分两个值相同的子数组。
- 2、可见数组值相加一定为偶数，所以和为奇数的数组直接舍弃。
- 3、找子集和为sum / 2的子数组即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % 2 == 1) return false;
int target = sum / 2;
vector<int> dp(n + 1, 0);
dp[0] = 1;
for(auto i : nums)
{
for(int j = target; j >= i; j--)
{
dp[j] = dp[j] || dp[j - i];
}
}
return dp[n];
}
};
|
复杂度
时间复杂度：O(n ^ 2)
空间复杂度：O(n)
参考文章
https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-a7dd/