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 Falsetarget = total_sum // 2memo = {}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)# 更新备忘录memomemo[(target, index)] = include or exclude# 返回结果return include or excludereturn 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 Falsetarget = total_sum // 2# 创建一个长度为target + 1的布尔型数组dp = [False] * (target + 1)dp[0] = True# 填充DP数组for num in nums:# 从target到num的每个子集和ifor 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)。相比纯递归法，备忘录法通过避免重复计算相同的子问题，大大提升了效率。