Python面试宝典第50题：分割等和子集
题目
给你一个只包含正整数的非空数组nums，请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1, 5, 11, 5]
输出：True
解释：数组可以分割成[1, 5, 5]和[11]。示例 2：
输入：nums = [1, 2, 3, 5]
输出：False
解释：数组不能分割成两个元素和相等的子集。
备忘录法
备忘录法的基本思想是：在递归过程中缓存已计算的结果，避免重复计算相同子问题。这样可以显著减少递归树的分支，提高算法效率。使用备忘录法求解本题的主要步骤如下。
1、定义递归函数can_partition_helper。该函数接受四个参数：数组nums、目标和target、当前索引index、备忘录memo。其中，备忘录memo用于存储已计算过的子问题的结果。
2、基本情况。
（1）如果target为0，则表示找到了一个子集，返回True。
（2）如果target小于0，或者index超出了数组范围，则表示无法找到合适的子集，返回False。
（3）如果target和index的组合已经存在于备忘录memo中，则直接返回备忘录中的结果。
3、进行递归。
（1）对于每个元素nums[index]，有两种选择：包含或不包含该元素。
（2）如果包含nums[index]，则递归调用can_partition_helper函数，计算剩余元素是否可以构成目标和target - nums[index]。
（3）如果不包含nums[index]，则递归调用can_partition_helper 函数，计算剩余元素是否可以构成目标和target。
（4）如果任一递归路径返回True，则更新备忘录memo，并返回True。
4、如果所有递归路径都返回False，则表示无法分割成两个子集，返回False。
根据上面的算法步骤，我们可以得出下面的示例代码。
def partition_equal_subset_sum_by_memoization(nums):
total_sum = sum(nums)
# 如果总和不是偶数，则无法分割成两个子集
if total_sum % 2 != 0:
return False
target = total_sum // 2
memo = {}
def can_partition_helper(nums, target, index):
# 如果target为0，则表示找到了一个子集
if target == 0:
return True
# 如果target小于0，或者index超出了数组范围，则表示无法找到合适的子集
if target < 0 or index >= len(nums):
return False
# 如果target和index的组合已经存在于备忘录中，则直接返回备忘录中的结果
if (target, index) in memo:
return memo[(target, index)]
# 包含nums[index]
include = can_partition_helper(nums, target - nums[index], index + 1)
# 不包含nums[index]
exclude = can_partition_helper(nums, target, index + 1)
# 更新备忘录memo
memo[(target, index)] = include or exclude
# 返回结果
return include or exclude
return can_partition_helper(nums, target, 0)
nums = [1, 5, 11, 5]
print(partition_equal_subset_sum_by_memoization(nums))
nums = [1, 2, 3, 5]
print(partition_equal_subset_sum_by_memoization(nums))动态规划法
使用动态规划法时，我们需要构建一个一维数组dp来存储达到每个子集和的可能性。数组dp的索引表示子集和，dp[i]表示能否通过选择数组中的元素达到和为i的子集。使用动态规划法求解本题的主要步骤如下。
1、初始化。计算数组nums的总和total_sum，如果total_sum不是偶数，则无法分割成两个子集，直接返回False。否则，计算目标和target为total_sum // 2。
2、构建DP数组。创建一个长度为target + 1的布尔型数组dp，其中dp[0]初始化为True，表示总和为0的子集始终存在，其他位置初始化为False。
3、填充DP数组。对于每个元素num，从target到num的每个子集和i，更新dp[i]为dp[i]或dp[i - num]。
4、返回dp[target]，表示是否存在和为目标和target的子集。
根据上面的算法步骤，我们可以得出下面的示例代码。
def partition_equal_subset_sum_by_dp(nums):
total_sum = sum(nums)
# 如果总和不是偶数，则无法分割成两个子集
if total_sum % 2 != 0:
return False
target = total_sum // 2
# 创建一个长度为target + 1的布尔型数组
dp = [False] * (target + 1)
dp[0] = True
# 填充DP数组
for num in nums:
# 从target到num的每个子集和i
for i in range(target, num - 1, -1):
# 更新dp[i]
dp[i] = dp[i] or dp[i - num]
return dp[target]
nums = [1, 5, 11, 5]
print(partition_equal_subset_sum_by_dp(nums))
nums = [1, 2, 3, 5]
print(partition_equal_subset_sum_by_dp(nums))总结
使用备忘录法时，每个子问题只被计算一次，子问题的数量与数组nums的长度、目标和target成正比。总的时间复杂度为O(N * target)，其中N是数组nums的长度，target是目标和的一半。备忘录的最大大小为N * target，故其空间复杂度为O(N * target)。相比纯递归法，备忘录法通过避免重复计算相同的子问题，大大提升了效率。