Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Generate all unique permutations of a collection that may contain duplicates — using backtracking with pruning.
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] <= 10The simplest approach: generate all permutations (including duplicates), collect them into a Set, and return the unique ones.
Standard permutation generates 3! = 6 results, but only 3 are unique:
This works but wastes time generating duplicates we'll throw away. For inputs with many duplicates, the waste becomes enormous.
Can we avoid generating duplicates in the first place? Yes — by sorting the input and adding a simple skip rule, we prune duplicate branches at the source.
The strategy has two parts: sort the array first, then during backtracking, skip duplicate values at the same tree level.
When building a permutation position by position, we use a used[] boolean array to track which elements are already placed. The pruning condition is:
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue }
if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue
if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue; }
if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;
This means: if the current value equals the previous one, and the previous one is not in use (meaning we already explored it at this level and backtracked), then skip — because choosing this element would produce the same subtree.
Think of it this way: among identical values, we enforce that they must be used in order (left to right in the sorted array). If the previous copy wasn't used, we can't jump ahead to this copy — that would be out of order and produce a duplicate permutation.
Let's trace through the backtracking tree for nums = [1, 1, 2] (already sorted). We label the positions as indices 0, 1, 2 corresponding to values 1, 1, 2.
Notice: Without pruning, choosing i=1 first (value 1) would generate the exact same subtree as choosing i=0 first (also value 1). The skip rule catches this at level 1 and prunes the entire branch, saving exponential work.
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); // Step 1: sort so duplicates are adjacent List<List<Integer>> result = new ArrayList<>(); backtrack(nums, new boolean[nums.length], new ArrayList<>(), result); return result; } private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) { if (path.size() == nums.length) { // Base case: full permutation built result.add(new ArrayList<>(path)); // Add a COPY (path will be modified) return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // Already in current path // SKIP RULE: same value as previous, and previous wasn't used // → we already explored this choice at this tree level if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; // Choose path.add(nums[i]); backtrack(nums, used, path, result); // Explore path.remove(path.size() - 1); // Un-choose (backtrack) used[i] = false; } } }
func permuteUnique(nums []int) [][]int { sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] }) // sort so duplicates are adjacent result := [][]int{} used := make([]bool, len(nums)) var backtrack func(path []int) backtrack = func(path []int) { if len(path) == len(nums) { // Base case: full permutation built tmp := make([]int, len(path)) copy(tmp, path) // Add a COPY (path will be modified) result = append(result, tmp) return } for i := 0; i < len(nums); i++ { if used[i] { continue } // Already in current path // SKIP RULE: same value as previous, and previous wasn't used // → we already explored this choice at this tree level if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue } used[i] = true // Choose path = append(path, nums[i]) backtrack(path) // Explore path = path[:len(path)-1] // Un-choose (backtrack) used[i] = false } } backtrack([]int{}) return result }
def permute_unique(nums: list[int]) -> list[list[int]]: nums.sort() # Step 1: sort so duplicates are adjacent result: list[list[int]] = [] used = [False] * len(nums) def backtrack(path: list[int]) -> None: if len(path) == len(nums): # Base case: full permutation built result.append(path[:]) # Add a COPY (path will be modified) return for i in range(len(nums)): if used[i]: # Already in current path continue # SKIP RULE: same value as previous, and previous wasn't used # → we already explored this choice at this tree level if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True # Choose path.append(nums[i]) backtrack(path) # Explore path.pop() # Un-choose (backtrack) used[i] = False backtrack([]) return result
impl Solution { pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> { nums.sort(); // Step 1: sort so duplicates are adjacent let mut result = Vec::new(); let mut used = vec![false; nums.len()]; let mut path = Vec::new(); backtrack_u(&nums, &mut used, &mut path, &mut result); result } } fn backtrack_u( nums: &[i32], used: &mut Vec<bool>, path: &mut Vec<i32>, result: &mut Vec<Vec<i32>>, ) { if path.len() == nums.len() { // Base case: full permutation built result.push(path.clone()); // Add a COPY (path will be modified) return; } for i in 0..nums.len() { if used[i] { continue; } // Already in current path // SKIP RULE: same value as previous, and previous wasn't used // → we already explored this choice at this tree level if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue; } used[i] = true; // Choose path.push(nums[i]); backtrack_u(nums, used, path, result); // Explore path.pop(); // Un-choose (backtrack) used[i] = false; } }
function permuteUnique(nums: number[]): number[][] { nums.sort((a, b) => a - b); // Step 1: sort so duplicates are adjacent const result: number[][] = []; const used: boolean[] = new Array(nums.length).fill(false); function backtrack(path: number[]): void { if (path.length === nums.length) { // Base case: full permutation built result.push([...path]); // Add a COPY (path will be modified) return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; // Already in current path // SKIP RULE: same value as previous, and previous wasn't used // → we already explored this choice at this tree level if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; used[i] = true; // Choose path.push(nums[i]); backtrack(path); // Explore path.pop(); // Un-choose (backtrack) used[i] = false; } } backtrack([]); return result; }
Enter numbers (may contain duplicates) and step through the backtracking process to see which branches are explored and which are pruned.
In the worst case (all distinct elements), we generate n! permutations, each requiring O(n) to copy, giving O(n! × n) time. When duplicates exist, the pruning reduces the unique permutation count to n! / (d1! × d2! × ...) where dk is the count of each distinct value. Space is O(n) for the recursion stack, used[] array, and current path (not counting the output).
Generate all n! permutations via standard backtracking (n branches at depth 1, n-1 at depth 2, etc.), then insert each into a HashSet for deduplication. Hashing each permutation costs O(n), and the set stores up to n! entries, wasting both time and memory on duplicates.
Sorting puts duplicates adjacent. The skip rule (nums[i]==nums[i-1] && !used[i-1]) prunes duplicate branches at each tree level before recursing, so only unique permutations are generated. The used[] array and recursion stack use O(n). Actual output count drops to n!/(d1!×d2!×...).
Sorting + skip-same-value prevents duplicates inline -- same worst-case time complexity, but avoids post-filtering entirely. For [1,1,1,1,1] (five 1s), brute force generates 120 permutations then deduplicates to 1. Our approach generates exactly 1 permutation directly -- the skip rule prunes 119 branches at the root level.
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.