如何修改数组等和子集划分的回溯代码，避免传递set1和set2参数？

核心思路 #

原代码通过传递两个子集的和来判断是否相等，其实可以简化成寻找一个子集的和等于数组总和的一半——因为如果存在这样的子集，剩下的元素和自然也等于总和的一半，刚好满足拆分条件。基于这个逻辑，我们只需要跟踪单个变量（当前子集的和），完全不需要传递两个参数。

具体修改步骤 #

1. 先判断数组总和是否为奇数：如果是，直接返回False（奇数无法拆分成两个相等的整数和）。
2. 计算目标值target为总和的一半，我们的目标就是找到一个子集的和等于这个值。
3. 回溯函数仅传递两个参数：当前遍历的索引i、当前已选元素的和current_sum。

修改后的代码 #

def canPartition(self, nums: List[int]) -> bool:
    total = sum(nums)
    # 总和为奇数，直接无法拆分
    if total % 2 != 0:
        return False
    target = total // 2

    def backtrack(i, current_sum):
        # 找到符合条件的子集，直接返回True
        if current_sum == target:
            return True
        # 遍历完所有元素还没找到，返回False
        if i >= len(nums):
            return False
        # 剪枝：当前和已经超过目标，不用继续递归
        if current_sum > target:
            return False
        
        # 选择当前元素，加入子集和
        choose = backtrack(i + 1, current_sum + nums[i])
        # 不选择当前元素，保持子集和不变
        not_choose = backtrack(i + 1, current_sum)
        # 只要有一条路径满足就返回True
        return choose or not_choose
    
    return backtrack(0, 0)

额外优化说明 #

原代码没有剪枝逻辑，当current_sum已经超过target时还会继续递归，修改后的代码加入了这个剪枝条件，能有效减少不必要的递归调用，提升效率。

内容的提问来源于stack exchange，提问作者Michael Xia