Skip to main content
Talentd

Permutations II - Solution & Explanation

MediumArrayBacktracking23 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array that may contain duplicates. The task is to return all unique permutations of the numbers. The challenge is avoiding duplicate permutations that naturally appear when identical values exist in the input array.

Approach 1: Backtracking with Used Array (O(n! * n) time, O(n) space)

This is the most common approach used in interviews. Start by sorting the array so duplicate numbers appear next to each other. During backtracking, maintain a used[] array that tracks which indices are already included in the current permutation path. When iterating through the array, skip a number if it is the same as the previous one and the previous copy was not used in the current branch. This rule prevents generating duplicate permutations. The recursion builds permutations step by step and adds them to the result once the path length reaches n. Time complexity is O(n! * n) because there are up to n! permutations and each permutation construction costs O(n). Space complexity is O(n) for the recursion stack and used array (excluding output).

Approach 2: Recursive Swap with Set (O(n! * n) time, O(n) space)

This approach generates permutations by swapping elements in place, similar to classic permutation generation. At each recursion level, iterate from the current index to the end and swap the chosen element into the current position. A local HashSet or set is used at each level to track which values have already been placed at that position. If a value has already been used in that level, skip it to prevent duplicate permutations. After exploring a branch, swap the elements back to restore the original array before continuing. This technique relies heavily on array manipulation and backtracking. The time complexity remains O(n! * n) because each permutation requires copying or recording the current array state, and the recursion depth is n. Space complexity is O(n) due to recursion depth and the per-level set.

Recommended for interviews: Backtracking with a used array and sorted input is the approach most interviewers expect. It clearly demonstrates how you handle duplicates while generating permutations. Starting with naive permutation generation shows baseline understanding, but adding the duplicate-skipping rule proves you understand pruning and efficient backtracking design. The swap-with-set approach is also valid but slightly less intuitive because duplicate control happens through an additional set at each recursion level.

Approach 1: Backtracking with Used Array

This approach uses backtracking to generate permutations and a boolean array to track used elements in the current permutation combination. By sorting the array at the start, we can easily skip duplicates.

This Python solution uses recursion and backtracking to generate permutations. Sorting the nums list initially helps to efficiently skip duplicates by checking if the element is the same as the previous one and if the previous one has been used.

Code

PythonJavaJavaScriptC#C

Python

Java

JavaScript

C#

C

Complexity

Time Complexity: O(n * n!) due to the generation of all permutations.
Space Complexity: O(n!) for storing the permutations and O(n) for the recursion stack.

Try this approach in the editor →

Approach 2: Recursive Swap with Set

This method carries out permutations by recursively swapping elements and employs a set to track unique permutations and avoid generating duplicate results. It does not require sorting initially but uses swaps directly to generate permutations.

Implementing permutations through swapping allows the program to manage the sequence in-place and recursively form permutations, collecting results in a set for uniqueness.

Code

PythonJavaJavaScriptC#

Python

Java

JavaScript

C#

Complexity

Time Complexity: O(n * n!)
Space Complexity: O(n * n!) because of the set used to store permutations.

Try this approach in the editor →

Approach 3: Sorting + Backtracking

We can first sort the array so that duplicate numbers are placed together, making it easier to remove duplicates.

Then, we design a function dfs(i), which represents the current number to be placed at the i-th position. The specific implementation of the function is as follows:

  • If i = n, it means we have filled all positions, add the current permutation to the answer array, and then return.
  • Otherwise, we enumerate the number nums[j] for the i-th position, where the range of j is [0, n - 1]. We need to ensure that nums[j] has not been used and is different from the previously enumerated number to ensure that the current permutation is not duplicated. If the conditions are met, we can place nums[j] and continue to recursively fill the next position by calling dfs(i + 1). After the recursive call ends, we need to mark nums[j] as unused to facilitate subsequent enumeration.

In the main function, we first sort the array, then call dfs(0) to start filling from the 0th position, and finally return the answer array.

The time complexity is O(n times n!), and the space complexity is O(n). Here, n is the length of the array. We need to perform n! enumerations, and each enumeration requires O(n) time to check for duplicates. Additionally, we need a marker array to mark whether each position has been used, so the space complexity is O(n).

Similar problems:

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Used Array

Time Complexity: O(n * n!) due to the generation of all permutations.
Space Complexity: O(n!) for storing the permutations and O(n) for the recursion stack.

Recursive Swap with Set

Time Complexity: O(n * n!)
Space Complexity: O(n * n!) because of the set used to store permutations.

Sorting + Backtracking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Used ArrayO(n! * n)O(n)Most common interview solution; easy duplicate pruning after sorting
Recursive Swap with SetO(n! * n)O(n)Useful when generating permutations in-place without a separate used array

Video Solution

Permutations II - Backtracking - Leetcode 47 • NeetCode • 125,326 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Permutations II easy or hard?
Permutations II is generally classified as a medium difficulty problem. Basic permutation generation is straightforward, but handling duplicates correctly requires careful pruning logic during backtracking. Many candidates struggle with the duplicate-skipping condition.
Permutations II Python/Java solution
Python and Java implementations usually follow the same pattern: sort the input array, track visited indices with a boolean array, and build permutations recursively. During iteration, skip numbers that are the same as the previous element if the previous element was not used in the current recursion path.
How to solve Permutations II in O(n)?
Permutations II cannot be solved in O(n) time because generating permutations inherently requires factorial work. Any correct algorithm must output every valid permutation, which is up to n! results. Efficient solutions focus on pruning duplicates using sorting or hash sets during backtracking.
What is the best approach for Permutations II?
Backtracking with a sorted array and a used[] tracking array is the most widely used solution. Sorting groups duplicates together, and the algorithm skips a number if it matches the previous number that was not used in the current recursion branch. This prevents duplicate permutations while still exploring all valid arrangements. Time complexity is O(n! * n).
Is Permutations II asked at Google/Amazon/Meta?
Permutation generation and duplicate-handling backtracking problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants include generating combinations, subsets with duplicates, and permutation generation with constraints. Interviewers use these problems to evaluate recursion and pruning strategies.
What data structure is used in Permutations II?
The solution primarily uses arrays and recursion. A boolean used[] array or a HashSet is typically added to control duplicates during backtracking. Sorting the array beforehand is also a key step because it allows simple duplicate checks during iteration.
What is the time complexity of Permutations II?
The time complexity is O(n! * n). There can be up to n! permutations in the worst case when all numbers are distinct, and building each permutation requires O(n) work. Duplicate values reduce the actual number of permutations but the upper bound remains factorial.

Ready to solve this problem?

Practice Permutations II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Next Permutation

Next

Number of Squareful Arrays