谁能找出这个 DFS 解决方案中的错误吗

Question

问题： 给定一组候选数字（candidates）和一个目标数字（target），找到候选数字中候选数字总和等于目标数字的所有唯一组合。 候选中的每个数字只能在组合中使用一次。 注意：解集不能包含重复的组合。

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]
 
Constraints:

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

我的解决方案： 由于这是一个回溯问题，我继续采用 dfs 方法，检查每个子序列及其总和，并相应地生成结果。为了处理重复的解决方案问题，我对

temp

数组进行排序，然后以元组的形式将其添加到结果集

result

中。

但事情是这样的；如果第一个示例工作正常，但我的方法在第二个示例中遇到了一个奇怪的问题。

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

第一个示例运行良好，但这是我得到的第二个示例的输出：

candidates =
[2,5,2,1,2]
target =
5

Output
[[1,2,2],[5],[1,1,2]]
Expected
[[1,2,2],[5]]

当输入数组中只有一个 1 时，有一个奇怪的元组

(1,1,2)

被添加到结果集中。我尝试过调试，但到目前为止还没有任何线索。

有人可以帮我找出哪里出错了吗？

......................................

Answer 1

正确的方法是使用 itertools

import itertools

candidates = [2,5,2,1,2]
target = 5

result = set()
candidates.sort()

result = set()

for i in range(1,len(candidates)+1):
   for seq in itertools.combinations(candidates,i):
      if sum(seq) == target:
         result.add(seq)

print(result)