Python集合递归实现子集和：代码偶现异常求排查

你的代码出现结果不稳定的原因有两个核心问题：

1. 集合的无序性导致递归路径不可控
   Python的集合是无序容器，set.pop()每次取出的元素是随机的，这会让每次运行时的递归分支选择完全不同——某次刚好选到能凑出目标和的元素路径就正常，某次选不到就异常，结果自然时好时坏。

2. 递归中直接修改原集合破坏了状态一致性
   你在递归里直接对传入的集合执行pop()操作，这会永久修改原集合的内容。当执行return checkForSubSet(set, sum - e) or checkForSubSet(set, sum)时，第一个递归调用已经把元素从集合中移除了，第二个递归调用拿到的是被修改后的集合，后续递归逻辑会因为元素丢失而完全偏离预期。

要解决这个问题，必须避免直接修改原集合，而是传递集合的副本，或者改用有序容器（比如列表）来处理：

方案1：使用集合副本递归 #

def check_for_subset(s, target_sum):
    if len(s) == 0 or target_sum < 0:
        return False
    # 取出一个元素（用next(iter(s))替代pop，不修改原集合）
    elem = next(iter(s))
    # 创建两个副本，分别对应包含/不包含当前元素的分支
    subset_with = s - {elem}
    subset_without = s.copy()
    subset_without.remove(elem)
    
    if target_sum == elem:
        return True
    # 递归检查两种情况
    return check_for_subset(subset_with, target_sum - elem) or check_for_subset(subset_without, target_sum)

if __name__ == '__main__':  
    input_set = {3, 34, 4, 12, 5, 2}
    target = 17
    if check_for_subset(input_set, target):
        print("Found a subset with given sum")
    else:
        print("No subset with given sum")

方案2：转成列表处理（更稳定） #

子集和问题用有序列表处理逻辑更直观，也能避免集合无序带来的不确定性：

def check_for_subset(arr, target_sum, idx=0):
    if target_sum == 0:
        return True
    if idx >= len(arr) or target_sum < 0:
        return False
    # 递归检查：包含当前元素的情况
    if check_for_subset(arr, target_sum - arr[idx], idx + 1):
        return True
    # 递归检查：不包含当前元素的情况
    return check_for_subset(arr, target_sum, idx + 1)

if __name__ == '__main__':  
    input_set = {3, 34, 4, 12, 5, 2}
    target = 17
    if check_for_subset(list(input_set), target):
        print("Found a subset with given sum")
    else:
        print("No subset with given sum")

• 不要用set作为变量名，这会覆盖Python内置的set类型，属于不良编码习惯。
• 集合在子集和问题中没有天然优势，反而因为无序性增加了调试难度，用列表处理会更可靠。

内容的提问来源于stack exchange，提问作者David Shandor