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
- Sort the array → so duplicates are adjacent.
- Use backtracking
Maintaina path (current permutation being built).- At each step, iterate over remaining
choices. - Skip duplicates If the current number is the same as the previous
(choices[i] === choices[i-1])→ continue. - Pick
choices[i], recurse with the rest of the elements, then backtrack.
- When path.length === arr.length, store it in result.
Time Complexity
Time Complexity = O(n * n!)
Space Complexity
Space Complexity = O(n * n!)
Dry Run
Input: digits = "23"
Initialize:
digits = "23"
letters = { 2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz" }
result = []
Call backtrack([], 0)
backtrack([], 0):
index = 0 → digits[0] = '2' → choices = "abc"
Loop i over "abc":
i = 0 → path = ['a']
→ backtrack(['a'], 1)
backtrack(['a'], 1):
index = 1 → digits[1] = '3' → choices = "def"
Loop i over "def":
i = 0 → path = ['a','d']
→ backtrack(['a','d'], 2)
index == digits.length → push "ad"
result = ["ad"]
path.pop() → ['a']
i = 1 → path = ['a','e']
→ backtrack(['a','e'], 2)
push "ae"
result = ["ad","ae"]
path.pop() → ['a']
i = 2 → path = ['a','f']
→ backtrack(['a','f'], 2)
push "af"
result = ["ad","ae","af"]
path.pop() → ['a']
End of inner loop, path.pop() → []
i = 1 → path = ['b']
→ backtrack(['b'], 1)
index = 1 → digits[1] = '3' → choices = "def"
Loop:
'd' → push "bd"
'e' → push "be"
'f' → push "bf"
result = ["ad","ae","af","bd","be","bf"]
path.pop() → []
i = 2 → path = ['c']
→ backtrack(['c'], 1)
digits[1] = '3' → choices = "def"
Loop:
'd' → push "cd"
'e' → push "ce"
'f' → push "cf"
result = ["ad","ae","af","bd","be","bf","cd","ce","cf"]
path.pop() → []
All recursive calls complete.
Return result = ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: The algorithm uses backtracking:
- For each digit, loop through the mapped letters.
- Append a letter, recurse to the next digit, then pop (backtrack).
- When
index === digits.length, join the path and push toresult.
var permuteUnique = function(arr) {
let result = [];
arr.sort((a,b) => (a-b));
let backtrack = (path, choices) => {
if(path.length === arr.length) {
result.push([...path]);
return;
}
for(let i=0; i 0 && choices[i] === choices[i-1])
continue;
path.push(choices[i]);
backtrack(path, [...choices.slice(0, i), ...choices.slice(i+1)]);
path.pop();
}
}
backtrack([], arr);
return result;
};
def permuteUnique(nums):
result = []
nums.sort()
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
import java.util.*;
class Solution {
public List> permuteUnique(int[] nums) {
List> result = new ArrayList<>();
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, boolean[] used, List path, List> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
path.add(nums[i]);
backtrack(nums, used, path, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
class Solution {
public:
vector> permuteUnique(vector& nums) {
vector> result;
sort(nums.begin(), nums.end());
vector path;
vector used(nums.size(), false);
backtrack(nums, used, path, result);
return result;
}
void backtrack(vector& nums, vector& used, vector& path, vector>& result) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, used, path, result);
path.pop_back();
used[i] = false;
}
}
};
void printPermutation(int* path, int size) {
for(int i = 0; i < size; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
void backtrack(int* nums, int numsSize, bool* used, int* path, int depth) {
if (depth == numsSize) {
printPermutation(path, numsSize);
return;
}
for (int i = 0; i < numsSize; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
path[depth] = nums[i];
backtrack(nums, numsSize, used, path, depth + 1);
used[i] = false;
}
}
int cmp(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int nums[] = {1, 1, 2};
int size = sizeof(nums) / sizeof(nums[0]);
qsort(nums, size, sizeof(int), cmp);
bool used[100] = {false};
int path[100];
backtrack(nums, size, used, path, 0);
return 0;
}
using System;
using System.Collections.Generic;
public class Solution {
public IList> PermuteUnique(int[] nums) {
var result = new List>();
Array.Sort(nums);
bool[] used = new bool[nums.Length];
Backtrack(nums, used, new List(), result);
return result;
}
private void Backtrack(int[] nums, bool[] used, List path, IList> result) {
if (path.Count == nums.Length) {
result.Add(new List(path));
return;
}
for (int i = 0; i < nums.Length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
path.Add(nums[i]);
Backtrack(nums, used, path, result);
path.RemoveAt(path.Count - 1);
used[i] = false;
}
}
}
