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]]


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


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.


1def permuteUnique(self, nums: List[int]) -> List[List[int]]:
2    used = [False] * len(nums)
3    ans = []
4    nums.sort()
6    def dfs(path_length, path):
7        if path_length == len(nums):
8            ans.append(path[:])
9            return
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()
20    dfs(0, [])
21    return ans

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns