难度: Medium
给你一个 只包含正整数 的 非空 数组 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
Submission
运行时间: 30 ms
内存: 16.0 MB
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# n = len(nums)
# total = sum(nums)
# if total & 1:
# return False
# target = total // 2
# # dp[i][j] 截止到索引i能否和为j
# # dp[i][j] = dp[i - 1][j - nums[i]] or dp[i - 1][j]
# dp = [[False] * (target + 1) for _ in range(n)]
# for i in range(n):
# dp[i][0] = True
# if nums[0] <= target:
# dp[0][nums[0]] = True
# for i in range(1, n):
# for j in range(1, target + 1):
# if j - nums[i] >= 0:
# dp[i][j] = dp[i - 1][j - nums[i]] or dp[i - 1][j]
# else:
# dp[i][j] = dp[i - 1][j]
# return dp[n - 1][target]
#巧妙解法，记录每一次x求和结果
s = sum(nums)
if s & 1:
return False
target = s >> 1
# dp的二进制数中，从左往右数，从0开始，第i位表示能否组成和为i的集合
dp = 1 << target
for x in nums:
dp |= dp >> x
# 提前返回答案
if dp & 1:
return True
return False
Explain
这个题解使用了动态规划的思路。首先判断数组的总和是否为奇数，如果是则不可能平分成两个等和子集。然后将目标和设为总和的一半。接下来使用一个整数dp作为状态，其二进制表示中从右往左第i位表示是否存在一个和为i的子集。通过遍历数组中的每个数x，将dp中所有已经置为1的位向右移动x位，再与原dp取或，这样就在dp中记录了当前数组前缀中所有可能的子集和。如果右移后dp的最低位变为1，说明存在一个子集的和等于目标和，直接返回True。遍历结束后，如果dp最低位仍为0，说明不存在符合条件的子集划分，返回False。
时间复杂度: O(n * target)
空间复杂度: O(1)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s & 1:
return False
target = s >> 1
# dp的二进制数中，从右往左数，第i位表示是否存在一个和为i的子集
dp = 1 << target
for x in nums:
# 将dp中所有已经置为1的位向右移动x位，再与原dp取或
dp |= dp >> x
# 如果右移后dp的最低位变为1，说明存在一个子集的和等于目标和，直接返回True
if dp & 1:
return True
# 遍历结束后，如果dp最低位仍为0，说明不存在符合条件的子集划分，返回False
return False
Explore
如果一个数组的总和是奇数，那么它不可能被划分为两个和相等的子集。因为两个相等的数相加的结果总是偶数，而奇数永远无法被2整除得到一个整数。所以，如果数组的总和是奇数，我们可以直接得出结论，不可能将其平分为两个等和的子集。
在这个问题中，使用位运算而不是传统的动态规划表可以大大减少空间复杂度。位运算通过利用整数的每一位来代表子集和的存在与否，可以使用更少的空间（仅需一个整数变量）存储状态信息。此外，位运算提供了非常高效的方式来更新状态，例如通过位移和位或操作来合并状态。这种方法在处理子集和问题时非常高效且节省空间。
这一位运算操作是动态规划解法中的核心。`dp |= dp >> x`操作的含义是：首先将dp右移x位，这代表将所有已经存在的子集和都加上新元素x的值，然后使用位或(|)操作将这个结果合并回dp。这样，如果之前存在某个和为i的子集，通过这个操作，就能得到一个新的和为i + x的子集。位或操作确保了dp在这些新的子集和位置上被设置为1，从而在不丢失任何已有信息的情况下更新了可能的子集和。
在这个题解中，dp的二进制表示中的每一位i表示是否存在一个子集的和为i。特别地，二进制的最低位（即第0位）表示和为0的情况。由于目标是判断是否存在一个子集的和等于数组总和的一半（target），这个值被设置在dp中的最高位。因此，判断最低位是否为1（即`if dp & 1`）实际上是在检查是否存在一个子集，其和恰好等于target。这是因为在初始化时，dp被设置为指向target的位，随后的操作可能会将这个位向右移动直到第0位，如果这个位为1，则表示存在这样的子集。