Permutations II solution and explanation
Google
9 more videos on this problem
Permutations II - Backtracking - Leetcode 47NeetCode · 11:47 · 125K views
Permutations 2 (LeetCode 47) | Full solution with backtracking examples | Study AlgorithmsNikhil Lohia · 13:49 · 23K views
Permutations 2 | Live Coding with Explanation | Leetcode - 47Algorithms Made Easy · 6:32 · 6K views
Baozi Training Leetcode solution 47 permutations IIBaozi Training · 10:12 · 2K views
Permutations II | Leetcode 47 | Backtracking Playlist | Live coding sessionCoding Decoded · 5:57 · 2K views
LeetCode: 47. Permutations II (Visualized)Code With Zi · 18:31 · 1K views
Leetcode 47 | Permutations IITech Traversal · 13:00 · 1K views
Permutations II Python Solution - LeetCode #47Professor Oakes · 4:39 · 932 views
Daily Leetcode #226: Nov 12, 2020 - 47. Permutations IIProgramming Live with Larry · 8:33 · 528 views
Permutations II | Leetcode 47 | Amazon Google Facebook interview questionSuper Lazy Coder · 14:01 · 331 views
The problem
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.
def permuteUnique(nums):
def backtrack(combination, used):
if len(combination) == len(nums):
results.append(list(combination))
return
for i in range(len(nums)):
if used[i] or i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
combination.append(nums[i])
backtrack(combination, used)
used[i] = False
combination.pop()
results = []
nums.sort()
backtrack([], [False] * len(nums))
return results
print(permuteUnique([1, 1, 2]))import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PermutationsUnique {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
Arrays.sort(nums);
backtrack(nums, new boolean[nums.length], new ArrayList<>(), results);
return results;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> results) {
if (current.size() == nums.length) {
results.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
used[i] = true;
current.add(nums[i]);
backtrack(nums, used, current, results);
used[i] = false;
current.remove(current.size() - 1);
}
}
public static void main(String[] args) {
PermutationsUnique pu = new PermutationsUnique();
System.out.println(pu.permuteUnique(new int[]{1, 1, 2}));
}
}function permuteUnique(nums) {
const results = [];
nums.sort((a, b) => a - b);
const backtrack = (combination, used) => {
if (combination.length === nums.length) {
results.push([...combination]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
continue;
}
used[i] = true;
combination.push(nums[i]);
backtrack(combination, used);
used[i] = false;
combination.pop();
}
};
backtrack([], Array(nums.length).fill(false));
return results;
}
console.log(permuteUnique([1, 1, 2]));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void backtrack(int* nums, int numsSize, bool* used, int* current, int pos, int** results, int* returnSize, int* returnColumnSizes) {
if (pos == numsSize) {
results[*returnSize] = malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; ++i) {
results[*returnSize][i] = current[i];
}
returnColumnSizes[*returnSize] = numsSize;
(*returnSize)++;
return;
}
for (int i = 0; i < numsSize; ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
used[i] = true;
current[pos] = nums[i];
backtrack(nums, numsSize, used, current, pos+1, results, returnSize, returnColumnSizes);
used[i] = false;
}
}
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
*returnColumnSizes = malloc(sizeof(int) * 1000);
int** results = malloc(sizeof(int*) * 1000);
int* current = malloc(sizeof(int) * numsSize);
bool* used = calloc(numsSize, sizeof(bool));
qsort(nums, numsSize, sizeof(int), cmpfunc);
backtrack(nums, numsSize, used, current, 0, results, returnSize, *returnColumnSizes);
free(current);
free(used);
return results;
}
int cmpfunc(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int nums[] = {1, 1, 2};
int size;
int* returnColumnSizes;
int** result = permuteUnique(nums, 3, &size, &returnColumnSizes);
for (int i = 0; i < size; ++i) {
for (int j = 0; j < returnColumnSizes[i]; ++j) {
printf("%d ", result[i][j]);
}
printf("\n");
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
class PermutationsUnique {
public IList<IList<int>> PermuteUnique(int[] nums) {
Array.Sort(nums);
var results = new List<IList<int>>();
Backtrack(nums, new bool[nums.Length], new List<int>(), results);
return results;
}
private void Backtrack(int[] nums, bool[] used, List<int> current, List<IList<int>> results) {
if (current.Count == nums.Length) {
results.Add(new List<int>(current));
return;
}
for (int i = 0; i < nums.Length; i++) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
used[i] = true;
current.Add(nums[i]);
Backtrack(nums, used, current, results);
used[i] = false;
current.RemoveAt(current.Count - 1);
}
}
static void Main() {
var solution = new PermutationsUnique();
var result = solution.PermuteUnique(new[] { 1, 1, 2 });
foreach (var perm in result) {
Console.WriteLine(string.Join(",", perm));
}
}
}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.
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.
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.
def permuteUnique(nums):
def backtrack(start):
if start == len(nums):
results.add(tuple(nums)) # add as tuple to ensure uniqueness
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
results = set()
backtrack(0)
return [list(result) for result in results]
print(permuteUnique([1, 1, 2]))import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class PermutionsUniqueSwapSet {
public List<List<Integer>> permuteUnique(int[] nums) {
Set<List<Integer>> results = new HashSet<>();
permute(nums, 0, results);
return new LinkedList<>(results);
}
private void permute(int[] nums, int start, Set<List<Integer>> results) {
if (start == nums.length) {
List<Integer> permutation = new LinkedList<>();
for (int num : nums) {
permutation.add(num);
}
results.add(permutation);
return;
}
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
permute(nums, start + 1, results);
swap(nums, start, i);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
PermutionsUniqueSwapSet pu = new PermutionsUniqueSwapSet();
System.out.println(pu.permuteUnique(new int[]{1, 1, 2}));
}
}function permuteUnique(nums) {
const results = new Set();
const backtrack = (start) => {
if (start === nums.length) {
results.add(nums.slice().toString());
return;
}
for (let i = start; i < nums.length; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]];
backtrack(start + 1);
[nums[start], nums[i]] = [nums[i], nums[start]];
}
};
backtrack(0);
return Array.from(results, r => r.split(',').map(Number));
}
console.log(permuteUnique([1, 1, 2]));using System;
using System.Collections.Generic;
class PermutationsUniqueSwapSet {
public IList<IList<int>> PermuteUnique(int[] nums) {
var results = new HashSet<string>();
Permute(nums, 0, results);
var listResults = new List<IList<int>>();
foreach(var res in results) {
var lst = new List<int>();
foreach(var c in res.Split(',')) {
lst.Add(int.Parse(c));
}
listResults.Add(lst);
}
return listResults;
}
private void Permute(int[] nums, int start, HashSet<string> results) {
if (start == nums.Length) {
results.Add(string.Join(",", nums));
return;
}
for (int i = start; i < nums.Length; i++) {
Swap(nums, start, i);
Permute(nums, start + 1, results);
Swap(nums, start, i);
}
}
private void Swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
static void Main() {
var solution = new PermutationsUniqueSwapSet();
var result = solution.PermuteUnique(new[] { 1, 1, 2 });
foreach (var perm in result) {
Console.WriteLine(string.Join(",", perm));
}
}
}Implementing permutations through swapping allows the program to manage the sequence in-place and recursively form permutations, collecting results in a set for uniqueness.
Time Complexity: O(n * n!)
Space Complexity: O(n * n!) because of the set used to store permutations.
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 thei-th position, where the range ofjis[0, n - 1]. We need to ensure thatnums[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 placenums[j]and continue to recursively fill the next position by callingdfs(i + 1). After the recursive call ends, we need to marknums[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:
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
ranges::sort(nums);
int n = nums.size();
vector<vector<int>> ans;
vector<int> t(n);
vector<bool> vis(n);
auto dfs = [&](this auto&& dfs, int i) {
if (i == n) {
ans.emplace_back(t);
return;
}
for (int j = 0; j < n; ++j) {
if (vis[j] || (j && nums[j] == nums[j - 1] && !vis[j - 1])) {
continue;
}
t[i] = nums[j];
vis[j] = true;
dfs(i + 1);
vis[j] = false;
}
};
dfs(0);
return ans;
}
};function permuteUnique(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans: number[][] = [];
const t: number[] = Array(n);
const vis: boolean[] = Array(n).fill(false);
const dfs = (i: number) => {
if (i === n) {
ans.push(t.slice());
return;
}
for (let j = 0; j < n; ++j) {
if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) {
continue;
}
t[i] = nums[j];
vis[j] = true;
dfs(i + 1);
vis[j] = false;
}
};
dfs(0);
return ans;
}func permuteUnique(nums []int) (ans [][]int) {
slices.Sort(nums)
n := len(nums)
t := make([]int, n)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if i == n {
ans = append(ans, slices.Clone(t))
return
}
for j := 0; j < n; j++ {
if vis[j] || (j > 0 && nums[j] == nums[j-1] && !vis[j-1]) {
continue
}
vis[j] = true
t[i] = nums[j]
dfs(i + 1)
vis[j] = false
}
}
dfs(0)
return
}impl Solution {
pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort();
let n = nums.len();
let mut ans = Vec::new();
let mut t = vec![0; n];
let mut vis = vec![false; n];
fn dfs(
nums: &Vec<i32>,
t: &mut Vec<i32>,
vis: &mut Vec<bool>,
ans: &mut Vec<Vec<i32>>,
i: usize,
) {
if i == nums.len() {
ans.push(t.clone());
return;
}
for j in 0..nums.len() {
if vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1]) {
continue;
}
t[i] = nums[j];
vis[j] = true;
dfs(nums, t, vis, ans, i + 1);
vis[j] = false;
}
}
dfs(&nums, &mut t, &mut vis, &mut ans, 0);
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking with Used Array | Time Complexity: O(n * n!) due to the generation of all permutations. |
| Recursive Swap with Set | Time Complexity: O(n * n!) |
| Sorting + Backtracking | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Used Array | O(n! * n) | O(n) | Most common interview solution; easy duplicate pruning after sorting |
| Recursive Swap with Set | O(n! * n) | O(n) | Useful when generating permutations in-place without a separate used array |
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.