题目:416. 分割等和子集
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
解题:
1、dp问题。将数组切分为等和子集,即是求任意个元素的和等于数组和的一半。使用dp数组,第i个元素表示任意个元素的和能否等于i。那么在任意一个dp[i-n](n为nums中任意元素)为True的情况下,dp[i] 为True。
代码
class Solution:
def canPartition(self, nums: List[int]) -> bool:
target = sum(nums)
if target % 2 == 1:
return False
nums.sort()
target = target // 2
dp = [False] * (target + 1)
dp[0] = True
for i, n in enumerate(nums):
for j in range(target, n - 1, -1):
if dp[j - n] == True:
dp[j] = True
print(dp)
return dp[-1]
PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。
PPS:还是得日更呀,总结一下总是好的。