class Solution {
public:
bool canPartition(vector<int>& nums) {
}
};
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100相似题目
原站题解
python3 解法, 执行用时: 1076 ms, 内存消耗: 13.4 MB, 提交时间: 2020-11-17 15:08:24
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# 恰好装满的0-1背包问题
s, n = sum(nums), len(nums)
if s % 2 == 1:
return False
cap = s // 2
dp = [False] * (cap + 1)
dp[0] = True
for i in range(1, n+1):
for j in range(cap, nums[i-1]-1, -1):
dp[j] = dp[j] or dp[j-nums[i-1]]
return dp[cap]