难度: Easy
给定一个非空的正整数数组 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.com/problems/partition-equal-subset-sum/
运行时间: 124 ms
内存: 16.7 MB
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
这个问题是一个典型的背包问题，具体来说是一个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 # 遍历完所有元素后，如果没有找到目标和，返回假
在尝试将集合分割成两个等和的子集时，如果集合的总和是奇数，那么不可能平分成两个等和的子集。因为两个相同的数相加不可能得到一个奇数。因此，检查总和是否为奇数是一个有效的提前终止算法的条件，如果总和为奇数，可以直接返回False，避免不必要的计算。
是的，集合`pre`的初始状态为空集合，代表初始时没有任何元素被选中，因此和为0。在第一次循环中，首先考虑的是数组中的第一个元素。将这个元素本身添加到集合`pre`中，意味着开始探索包含该元素的可能的子集和。这是必要的，因为任何子集的和都必须从某个具体的元素开始累加，这确保了算法能够覆盖所有通过这些元素组合形成的可能和。
是的，当使用`pre.add(p + num)`时，可能会有重复计算的情况出现，尤其是当数组中有重复元素时。为了避免重复计算，可以在每次遍历新元素时，首先将所有可能形成的新和存储在一个临时集合中，然后再将这些新和添加到主集合`pre`中。这样做可以确保即使当前元素与之前的元素相同，其计算出的新和也只在这一轮被计算和添加一次。