The O(n) Club: Permutations: All The Things! (LeetCode 46 & The Backtracking Dance)

The O(n) Club: Permutations: All The Things! (LeetCode 46 & The Backtracking Dance)

⚡ TL;DR

Take a bunch of distinct integers and churn out every possible ordering. Backtracking is your golden ticket—no Java magic, just pick, recurse, and pray you remembered to backtrack.

// Brute-force (and totally allowed for n ≤ 6)
public List<list>> permute(int[] nums) {
    List<list>> results = new ArrayList<>();
    backtrack(new ArrayList<>(), nums, results);
    return results;
}
private void backtrack(List
<integer> path, int[] nums, List<list>> results) {
    if (path.size() == nums.length) {
        results.add(new ArrayList<>(path));
        return;
    }
    for (int num : nums) {
        if (path.contains(num)) continue; // already used
        path.add(num); // pick
        backtrack(path, nums, results); // go deeper
        path.remove(path.size() - 1); // back up (backtrack)
    }
}</list></integer></list></list>

🧠 How Devs Usually Mess This Up

This is where developers detour into the Bermuda Triangle. Common fumbles:

• Permutations vs. Combinations: News flash: order does matter. [1,2,3] ≠ [3,2,1]. Sorting and calling it done is cheating yourself.
• Worrying About Duplicates: Just chill. Problem says all inputs are unique, so you can stop writing duplicate filters no one asked for.
• Reusing Lists: Mutating your path without copying makes recursion behave like a toddler with permanent markers. Make a copy, clean up after yourself, or debug forever.

🔍 What’s Actually Going On

Imagine lining up for a group selfie, insisting every person stands in every possible spot with everyone else. Someone says, “let’s try me in the middle!”—again and again. That’s permutations. Try every slot for every person, undo your last photo, and do it all again like it’s your side gig. This is basically a recursive lineup with a very caffeinated photographer.

🛠️ PseudoCode

• Start empty: path = []
• Loop through all candidates: for each num in input array,
• If it’s already in path, skip it: nobody likes the guy who photobombs twice
• Add num to path, recurse: keep building that arrangement
• When path matches array length, save a copy to results: results.add(new ArrayList<>(path))
• Backtrack: Remove last number to try something else

💻 The Code

import java.util.*;
 public class Permutations {
    public List<list>> permute(int[] nums) {
        List<list>> results = new ArrayList<>();
        backtrack(new ArrayList<>(), nums, results);
        return results;
    }
    private void backtrack(List
<integer> path, int[] nums, List<list>> results) {
        if (path.size() == nums.length) {
            results.add(new ArrayList<>(path));
            return;
        }
        for (int num : nums) {
            if (path.contains(num)) continue;
            path.add(num);
            backtrack(path, nums, results);
            path.remove(path.size() - 1);
        }
    }
}</list></integer></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Cases: No input? Return [[]]. Singleton? Return [[num]]. More than 8 inputs? Hope you like factorials!
• Time/Space: n! (yes, that explodes fast). Six numbers means 720 results. Stay humble, stay small.
• Don’t Mutate in Place: Always copy lists before saving. Or watch your results mutate themselves like AI art gone rogue.
• path.contains(num): O(n) per check, but for small n, we’ll just ignore the performance alarm bells.

🧠 Interviewer Brain-Tattoo

“A permutation is just a combination—except you never get to relax, and your recursion stack’s about to go stress-test your JVM.”