LeetCode 39. 组合和 - 如何避免重复

Question

我正在做 leetcode 39. 组合总和。：

给定一个不同整数候选者数组和一个目标整数目标，返回所有唯一组合的列表 候选人 所选数字总和为 目标。您可以按任何顺序返回组合。

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

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

约束

• 1 <=候选人.length <= 30
• 1 <= 候选人[i] <= 200
• 候选的所有元素都不同。
• 1 <= 目标 <= 500

我能够编写以下代码：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        output = []
        
        def backtrack(currNbr, comb):
            if currNbr == 0:
                output.append(comb.copy())
                return
            elif currNbr < 0:
                return
            
            for nbr in candidates:
                comb.append(nbr)
                currNbr = currNbr - nbr
                backtrack(currNbr, comb)
                comb.pop()
                currNbr = currNbr + nbr
                
        backtrack(target, comb = [])  
        
        return output
        

但是，我无法对其进行排序以避免重复。我在网上看到了一些解决方案，但它们似乎都使用索引i。谁能向我解释一下如何更改我的代码以避免重复？

Answer 1

是的，使用索引 i 是很常见的。这是因为，一旦您迭代到组合的下一个nbr，在更深的递归中，不应该从combinations中选择一个条目< em>在此处选择的之前。

您可以在没有 i 的情况下执行此操作，而是传递 combinations 的缩短副本，其中仅包含仍允许选择的条目。

有几种方法可以做到这一点。当您还想缩短列表时，应该注意正确地迭代列表。此外，pop() 比 pop(0) 更高效。所以我选择使用 reversed 以相反的顺序迭代：

        def backtrack(candidates, currNbr, comb):   # Extra parameter
            if currNbr == 0:
                output.append(comb.copy())
                return
            elif currNbr < 0:
                return
            
            for nbr in reversed(candidates):  #  Reversed iteration 
                comb.append(nbr)
                backtrack(candidates[:], currNbr - nbr, comb)  # Pass a copy
                comb.pop()
                candidates.pop()  # The discarded element should not be used 
                
        backtrack(candidates, target, comb = [])  #  Extra argument