class Solution {
public:
bool canPartition(vector<int>& nums) {
}
};
剑指 Offer II 101. 分割等和子集
给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：nums 可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：nums 不可以分为和相等的两部分
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
注意：本题与主站 416 题相同： https://leetcode.cn/problems/partition-equal-subset-sum/
原站题解
python3 解法, 执行用时: 5240 ms, 内存消耗: 45.4 MB, 提交时间: 2022-05-24 17:23:25
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2 == 1: return False
target = s // 2
l = len(nums)
# dp[i][j]表示在nums里选择i个数相加得到的不超过j的最大数
dp = [[0 for j in range(0, target+1)] for i in range(0, l+1)]
for i in range(1, l+1):
for j in range(1, target+1):
dp[i][j] = dp[i-1][j]
if j >= nums[i-1]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])
return dp[l][target] == target