关于 LeetCode-39 的问题：'Combination Sum'

Question

测验 39. 给定一组不同的整数候选和一个目标整数目标，return 候选的所有唯一组合的列表，其中所选数字总和为目标。您可以 return 任意顺序组合。

可以无限次地从候选人中选择相同的数字。如果至少一个所选数字的频率不同，则两个组合是唯一的。

对于给定的输入，保证总计为目标的唯一组合的数量少于 150 个组合。

ex) [2,3,5] , 8 -> [2,2,2,2], [2,3,3], [3,5]

我使用深度优先算法递归地为此测验编写了 python 代码，这与正确答案相似，但略有不同。我写的东西不能正常工作。我的答案和正确答案只有一处不同，我找不到我的错误原因。

def combinationSum(candidates, target: int): # cnadidates : [2,3,5], target = 8
    
    result = []

    def dfs(index : int, path : list, remain : int):

        if remain < 0: # failed to find, prune this path!
            return
        
        if remain == 0: # successed!
            result.append(path)
            return

        ''' my code - wrong
        path += [candidates[index]]
        remain -= candidates[index]

        for i in range(index, len(candidates)):
            dfs(i, path, remain)
        '''

        ''' correct answer
        for i in range(index, len(candidates)):
            dfs(i, path + [candidates[i]], remain - candidates[i])
        '''
        
    dfs(0, [], target)

    return result


r = combinationSum([2,3,5] , 8)
print(r)

Answer 1

你的代码有几个问题： += 就地更改列表，这与 path+[something] 有很大不同。虽然可能，但在递归调用中通常不希望这样做。您的代码总是减去 candidates[index] 而正确答案动态地减去 candidates[i]

关于 LeetCode-39 的问题：'Combination Sum'

Question about LeetCode-39 : 'Combination Sum'

python

depth-first-search