Problem: 416. 分割等和子集
Reference
代码随想录 (programmercarl.com)
思路
一个典型的01背包问题。
这里我们使用一维背包，使用一维背包要注意：
- 先遍历物品在遍历背包
- 遍历背包需要倒序遍历
dp数组含义：大小为j的子集能装的数之和为dp【j】。
递推公式：dp【j】 = max(dp【j】，dp【j - nums【i】 】+ nums【i】)；
初始化：dp【0】 = 0；
遍历顺序：上面提到了。
能装得下是大于等于if(j >= nums[i])
不是大于 if(j > nums[i])
不要漏了😓
复杂度
时间复杂度:
添加时间复杂度, 示例： $O(n)$
空间复杂度:
添加空间复杂度, 示例： $O(n)$
Code
[]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for(int item : nums) {
sum += item;
}
if(sum % 2 == 1) return false;
int target = sum / 2;
vector<int> dp(target + 1);
for(int i = 0; i < nums.size(); i++) {
for(int j = target; j >= 0; j--) {
if(j >= nums[i]) {
dp[j] = std::max(dp[j],dp[j - nums[i]] + nums[i]);
}
}
}
return dp[target] == target;
}
};
|