🔀

Permutations — Every Element in Every Position

Use a boolean[] used array to mark which elements are already in the current permutation. At each recursive call, try every unused element. When curr.size() == n, a complete permutation is found.

🔀 n! Permutations ✅ used[] Array 📋 Collect at Leaf Time O(n!·n) Space O(n)

📋 When to Use

Generate all n! orderings of distinct elements
Track which elements are already chosen with boolean[] used
Unlike subsets: every element must be used, and order matters
Collect new ArrayList<>(curr) only when curr.size() == nums.length (at leaves)
Letter Combinations: same pattern, but pick from a char map for each digit

💡 Unlike subsets, here the loop always starts at i=0 every call — but skips used[i]. This ensures every element can appear in any position.

⚡ Complexity

Time

O(n!·n)

Space

O(n)

n! permutations × O(n) to copy each list = O(n!·n) time.
Recursion depth = n (one level per element chosen).
used[] and curr both hold at most n elements.
Space O(n) — excluding the output list.

Problem Given nums = [1,2,3], generate all permutations. At each level pick any unused element tracked by a boolean[] used array. Collect when path length == n. Backtrack by un-marking the element after recursion returns.
Input: nums = [1,2,3] · Answer: [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

Step 0 / 10

🔍 Init 🔄 Try Element 🌟 Found! ↩ Backtrack ✅ Done

🔀 Permutations: try every unused element at each level. Use boolean[] used to track which elements are in the current path. Collect when curr.size() == n.

backtrack(new ArrayList<>());

🌳 Recursion Tree — nums = [1, 2, 3]

active

in stack

leaf found

default

📚 Call Stack

— empty —

📥 Input Array — nums[i] / used[i]

🔗 curr:

[ ]

📋 Result:

[ waiting... ]

🧩 Pattern Skeleton Java 8

// ─── Permutations (distinct elements) ─────────────────
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];

void backtrack(List<Integer> curr) {
    if (curr.size() == nums.length) {       // leaf: complete permutation
        result.add(new ArrayList<>(curr));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;              // skip already-chosen
        used[i] = true;
        curr.add(nums[i]);                  // choose
        backtrack(curr);                    // explore
        curr.remove(curr.size() - 1);      // un-choose
        used[i] = false;
    }
}

🎯 Practice Problems

#46 Permutations 🔀 used[] backtrack Medium #47 Permutations II 🔀 sort + skip used[i-1] same val Medium #22 Generate Parentheses 🔀 constrained permutation (open ≤ n, close ≤ open) Medium #17 Letter Combinations of a Phone Number 🔀 pick from char map per digit Medium