这个问题是一个典型的背包问题,具体来说是一个0/1背包问题的变形,即确定一个集合中是否可以找到一些数,它们的和等于集合总和的一半。首先,如果集合的总和是奇数,那么不能平分成两个等和的子集。如果总和是偶数,我们将问题转化为寻找子集和是否可以达到总和的一半。使用一个集合`pre`来记录可以通过当前考虑的元素累加得到的所有可能的和。对于数组中的每一个数,我们更新这个集合,包括当前数本身和它与集合中已有元素的和。如果在任一时刻集合中出现了目标值(总和的一半),则说明可以分割成两个等和的子集。
时间复杂度: O(n*2^n)
空间复杂度: O(2^n)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums) # 计算数组的总和
if total % 2: # 如果总和是奇数,则不能平分
return False
target = total // 2 # 计算目标和,即总和的一半
pre = set() # 初始化集合,用来存储可能的子集和
for num in nums: # 遍历数组中的每个元素
for p in list(pre): # 遍历当前已有的和
pre.add(p + num) # 将当前元素加到已有的和上,形成新的和
pre.add(num) # 把当前元素本身也加入集合
if target in pre: # 如果目标和出现在集合中,直接返回真
return True
return False # 遍历完所有元素后,如果没有找到目标和,返回假