组合总和II问题DFS解法错误排查：为何出现不存在的元素组合？

问题描述 #

给定候选数集合（candidates）和目标数（target），找出candidates中所有和为target的唯一组合，每个候选数在组合中只能使用一次，且解集不能包含重复组合。

示例1 #

输入：candidates = [10,1,2,7,6,1,5], target = 8
输出：

[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例2 #

输入：candidates = [2,5,2,1,2], target = 5
输出：

[
[1,2,2],
[5]
]

约束条件 #

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

我的解法及问题 #

这是一个回溯问题，我采用DFS方法，检查每个子序列及其和来生成结果。为处理重复解问题，我将temp数组排序后以tuple形式存入结果集合result。

该解法在示例1中运行正常，但在示例2中出现异常：输入candidates = [2,5,2,1,2], target = 5时，输出为[[1,2,2],[5],[1,1,2]]，而预期输出是[[1,2,2],[5]]，出现了输入中不存在的元素组合[1,1,2]。

我的代码如下：

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(ind, temp, sum):
            if ind >= n:
                if sum == target:
                    temp.sort()
                    result.add(tuple(temp))
                return
            if sum < target:
                temp.append(candidates[ind])
                sum += candidates[ind]
                dfs(ind + 1, temp, sum)
                temp.pop()
                sum -= candidates[ind]
            dfs(ind + 1, temp, sum)
        temp, n = [], len(candidates)
        result = set()
        dfs(0, temp, 0)
        return result

错误原因排查 #

你的代码出现错误的核心原因有两个：

1. 原地修改共享列表导致递归路径混乱
   你在终止条件中使用temp.sort()对列表进行原地排序，但temp是所有递归分支共享的可变列表对象。排序操作会直接改变temp的元素顺序，后续的pop和append操作都会基于这个已排序的列表执行，从而生成不符合输入的错误组合（比如示例2中的[1,1,2]，就是因为列表顺序被破坏后，后续递归的元素选择逻辑混乱导致的）。

2. sum变量的冗余修改无意义
   Python中整数是不可变类型，你对sum执行的+=和-=操作只会修改当前函数栈内的局部变量，不会影响外层递归的sum值，这部分代码完全冗余，还容易造成逻辑混淆。

修正后的代码 #

优化版本（提前排序+跳过重复元素，无需集合去重） #

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 提前排序，方便跳过重复元素，减少无效递归
        candidates.sort()
        result = []
        
        def dfs(ind, temp, current_sum):
            if current_sum == target:
                result.append(temp.copy())
                return
            if ind >= len(candidates) or current_sum > target:
                return
            
            # 选择当前元素
            temp.append(candidates[ind])
            dfs(ind + 1, temp, current_sum + candidates[ind])
            temp.pop()
            
            # 跳过所有重复的当前元素，避免生成重复组合
            while ind + 1 < len(candidates) and candidates[ind] == candidates[ind + 1]:
                ind += 1
            # 不选择当前元素，直接跳到下一个不同的元素
            dfs(ind + 1, temp, current_sum)
        
        dfs(0, [], 0)
        return result

保留集合去重的修正版本 #

如果想保留集合去重的思路，只需将原地排序改为生成新列表，不修改原temp：

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = set()
        
        def dfs(ind, temp, current_sum):
            if current_sum == target:
                # 生成新的排序列表，不修改原temp
                result.add(tuple(sorted(temp)))
                return
            if ind >= len(candidates) or current_sum > target:
                return
            
            # 选择当前元素
            temp.append(candidates[ind])
            dfs(ind + 1, temp, current_sum + candidates[ind])
            temp.pop()
            
            # 不选择当前元素
            dfs(ind + 1, temp, current_sum)
        
        dfs(0, [], 0)
        return [list(item) for item in result]

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