LeetCode 39. Combination Sum - How to avoid duplicates

Question

I am doing leetcode 39. Combination Sum.:

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

I was able to write the following code:

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
        

However, I cannot make it in sort to avoid duplicates. I have seen some solutions online but they all seem to use an index i. Can anyone please explain to me, how to change my code to avoid duplicates?

Answer 1

Yes, it is common to make use of the index i. This is because once you iterate to the next nbr of combinations, nowhere in the deeper recursion, should an entry be selected from combinations that comes before the one selected here.

You can do this without i, and instead pass a shortened copy of combinations, which will only have those entries which are still allowed to be selected.

There are several ways to do this. One should take care of correctly iterating over a list when you also want to make it shorter. Also, pop() is more efficient than pop(0). So I have opted to use reversed to iterate in reversed order:

        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