LeetCode Permutations II Solution

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

Problem Link: https://leetcode.com/problems/permutations-ii/



Solution

Let's fill in the logic for backtracking1:

  • path_length: indicates the number of elements in path
  • used: an array storing the status of whether an element is used.
  • is_leaf: path_length == len(nums), when path_length is the same as nums's length.
  • get_edges and is_valid: all elements that are unused (used[i]==Flase).

In the implementation, we use an array used to store the whether an element has been used or not. Everytime we use a number, we add it into the path and we mark it used (used[idx] = True). Since there are duplicate values, let's apply methods in Deduplication to deduplicate the results. we want to sort the nums array so that duplicate elements are consecutive, and only proceed when the current element is the first of its occurrance.

Implementation

1def permuteUnique(self, nums: List[int]) -> List[List[int]]:
2    used = [False] * len(nums)
3    ans = []
4    nums.sort()
5    
6    def dfs(path_length, path):
7        if path_length == len(nums):
8            ans.append(path[:])
9            return
10        
11        for i in range(0, len(nums)):
12            if used[i]: continue
13            if(i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue
14            path.append(nums[i])
15            used[i] = True
16            dfs(path_length + 1, path)
17            used[i] = False
18            path.pop()
19    
20    dfs(0, [])
21    return ans