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

Question

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Constraints

1 <= candidates.length <= 30

1 <= candidates[i] <= 200

All elements of candidates are distinct.

1 <= target <= 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。这是因为一旦你迭代到 combinations 的下一个 nbr，在更深层次的递归中，任何地方都应该从之前中选择一个条目] 这里选的那个

您可以在没有 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

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

LeetCode 39. Combination Sum - How to avoid duplicates

python

combinations

backtracking

depth-first-search

Constraints