#47
Permutations II
Medium Backtracking with duplicate skip
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return all distinct orderings of an array that may contain duplicates.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: distinct orderings when numbers repeat.
Why this works: sort, and only use a duplicate if its earlier twin is already used. That fixes the order of equal values, so each arrangement is built once.
Example: [1, 1, 2]
[1, 1, 2], [1, 2, 1], [2, 1, 1]✦Hints open one at a time
Sort first.
Use a duplicate value only if its previous equal copy is already used in the current path.
↗Approach
Like Permutations, plus: skip nums[i] when i > 0, nums[i] == nums[i − 1] and !used[i − 1]. This forces equal values to be placed in index order, so each distinct permutation is built once.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) {
res.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; // keep equal values in order
used[i] = true;
path.add(nums[i]);
backtrack(nums, used, path, res);
path.remove(path.size() - 1);
used[i] = false;
}
}
}!Common mistake
Collecting into a Set to remove duplicates — it works, but generates n! permutations anyway.
Complexity
- Time: O(n · n!).
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon