LeetCode 47 — Permutation II

This article will talk about how to use backtracking to solve Leetcode #47, Permutations II.

This problem is similar to #46, Permutations. The only difference is that the numbers are not unique in this problem. It means that there might be several numbers in the list that are the same, such as [1,1,2].

Solution 1: Modification from #46

In theory, we can use the same solution in #46 to solve this problem. The only modification is that we need to use set() for storing the output, and check whether the new combination is already in the output. If “Yes”, then we ignore it. If “No”, then we add it into the output.

# Example
output = set()
...
if tuple(nums) not in output:
    output.add(tuple(nums[:]))

However, it will check all the possible combinations, even the combination is already added. For example, [1,1,2] will appear twice. The first combination is that the first “1” is selected as the first number. The second combination is that the second “1” is selected as the first number. These two combinations are exactly the same. So, we might want to avoid this condition happening.

Solution 2: Use Counter to avoid duplication

The idea is to use Counter to record the unique number and the remaining count of each number.

We first calculate the count of each number in the input list “nums”, then put it into the traverse function.

Then we iterate over the unique numbers in the counter to assign them as the next number in the cur_comb. Once we add a number into cur_comb, we reduce the count of this number in the counter. When the length of cur_comb reaches the length of the input, it means that the current combination is completed. We can add it to the output list.

Then we return to the previous step and pop out the last number and add the count back to the counter. In this way, this number will be added to the next position. For example, we are adding a number to the second position, when the number is already used (return from traverse and add back to counter), it will be kept for the third position since it was already added in some combination in the second position. It’s the turn for another number to be assigned to the second position.

# input is nums
# nums = [1, 1, 2]
n = len(nums)
def traverse(cur_comb, counter):
    if len(cur_comb) == n:
        output.append(cur_comb[:])
    for cur_num in counter:
        if counter[cur_num] > 0:
            # still need to add this number
            cur_comb.append(cur_num)
            counter[cur_num] -= 1
            traverse(cur_comb, counter)
            cur_comb.pop()
            counter[cur_num] += 1
output = []
traverse([], Counter(nums))

I think solution 2 is a little bit difficult than solution 1, but it is absolutely a better solution in terms of speed. Moreover, it is a good practice for the recursion.