The O(n) Club: Unique Permutations Without The Awkward Duplicates

The O(n) Club: Unique Permutations Without The Awkward Duplicates

⚡ TL;DR

Your regular permutation code doesn’t handle duplicates—it just embarrasses itself with repeated answers. Sort. Backtrack. Skip duplicates. Example?

// Wrong: prints many repeats
List<list>> permute(int[] nums) {
    //... naive attempt ...
}
 // Do this instead:
Arrays.sort(nums);
// ...then backtrack with skip logic</list>

🧠 How Devs Usually Mess This Up

The classic goof? Copying your “Permutation I” backtracking code, then acting shocked when you see two dozen [1,2,2] solutions in the output. Sorting is ignored, skip logic is skipped, and your interviewer’s eyebrow creeps higher with every duplicate. Pro tip: This isn’t one of those “it passes by accident” moments.

🔍 What’s Actually Going On

Imagine you’re making word anagrams out of tile pieces, but you’ve got twins: two ‘A’ tiles. If you don’t track which ‘A’ already joined, you end up with “AAB” and “AAB” both grinning at you. The trick? Only use a duplicate if its twin has been used earlier in your current arrangement. That’s why sorting helps—all the twins sit together at roll call.

🛠️ PseudoCode

• Sort the array first.

  Arrays.sort(nums);

  No sort, no correct result.
• Track usage of each index with boolean[] used.
• For each index i in the array:
  • If used[i], skip—this value’s played its part already.
  • If i > 0 && nums[i]==nums[i-1] && !used[i-1], skip—this prevents the “twin cousin” problem.
  • If not skipped, add nums[i] to path, mark used[i]=true, and call backtrack().
  • After recursion, unmark and remove, like a polite guest cleaning up.
• Add to results when the path is full.

💻 The Code

import java.util.*;
 public class PermutationsII {
    public List<list>> permuteUnique(int[] nums) {
        List<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
<integer> path, List<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;
            path.add(nums[i]);
            used[i] = true;
            backtrack(nums, used, path, result);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}</list></integer></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• Didn’t sort before? Your code is chaos incarnate.
• Skipped only by value, not also by previous usage? Welcome to the world of missing results and weird duplicates!
• Time complexity is still O(n!). Don’t sweat about performance—it’s by design, input’s small.
• Memory: Yes, you hold all permutations. That’s the gig.

🧠 Interviewer Brain-Tattoo

“If you copy permutations code without duplicate logic, your output isn’t unique—it’s just uniquely wrong.”