Q47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

 

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

This question is not super tricky to solve but it does need a thorough thought of the problem. I will state what I originally have and what is actually the nice solution of the problem.

At first, I was thinking about the following way to generate all possible permutations. Suppose we have all permutations using the first N numbers then the way to add one more is to insert it to the possible (N + 1) positions of each of the current permutation. If there is no duplicated numbers, this strategy works well. But with duplicated numbers, I need to check whether the permutation is duplicated. How to do it? Have a dictionary on the sequences which looks like an ugly fix.

OK, here comes the nicer solution provided by Leetcode. The fundamental difference is about how to form the permutations. Their strategy is to enumerate length K permutation using K of the N numbers and keep increasing K. So, at each step, they append one more number to the end of each sequence where the new number is from the leftover numbers (which have not been used). Why this strategy avoids duplication? Since at each step, if we assume the current length K sequences are unique, then we could make sure the new length (K + 1) sequences are also unique since we are appending different number at the end of different sequence which will not result in any duplicated sequences.

How to implement it? We need to write a recursion where

1. Select a number among the current unused numbers and update the list of unused numbers.
2. Add this number to all the current sequences.
3. Call the same recursion with these updated sequences and unused numbers.

Another tricky for maintaining the unused number is to use a data structure representing the count of each number.

The Python submission.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        count_dict = { i: 0 for i in range(-10, 11) }
        for n in nums:
            count_dict[n] += 1
        return self.get_perm([[]], count_dict)
    def get_perm(self, curr_perm, num_dict):
        res = []
        for k, v in num_dict.items():
            if v > 0:
                curr_perm_new = []
                for cc in curr_perm:
                    curr_perm_new.append(cc.copy() + [ k ])
                num_dict_new = num_dict.copy()
                num_dict_new[k] -= 1
                res += self.get_perm(curr_perm_new, num_dict_new)
        if len(res) == 0:
            return curr_perm
        return res

There is a name for this type of enumeration strategy which is called backtracking. To make it concrete here, it builds up the solution incrementally by adding something into the solution (“append another number to the end”) and updating the current available resources (“unused numbers”).

I quoted the backtracking sentence here (see link):

As a reminder, backtracking is a general algorithm for finding all (or some) solutions to some problems with constraints. It incrementally builds candidates to the solutions, and abandons a candidate as soon as it determines that the candidate cannot possibly lead to a solution.

Also, more backtracking questions are listed here.