Permutations

1. Problem & Core Objective

Given an array of distinct integers, return all possible permutations, in any order.

nums = [1,2,3]
→ [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]      3! = 6

Constraints: 1 <= nums.length <= 6 · -10 <= nums[i] <= 10 · all distinct

What's actually being tested: that permutations need no start index — and understanding why. In combinations, order doesn't matter so the index must only increase; in permutations, order is the answer, so every unused element is a candidate at every position.

2. First-Principles Thought Process

Count first

n choices for the first position, n − 1 for the second, and so on: n! permutations. At n = 6 that's 720 — small, which is why the constraint is so tight. At n = 12 it's 479 million.

The structural difference from combinations

Subsets and Combination Sum both used a start index, so the loop only ever moved forward. That was deliberate: it forced index order to be non-decreasing, which made [1,2] and [2,1] the same path.

Here that's exactly wrong. [1,2,3] and [2,1,3] are different answers. So the loop must consider every element at every level — no start index.

What replaces it

If the loop scans everything, something must stop an element being used twice in one permutation. Two ways:

A used[] boolean array — mark on choose, unmark on un-choose. Explicit and O(1) to test.

Swapping in place — at depth d, swap each candidate into position d, recurse, swap back. No extra array, and the prefix [0..d) holds the permutation so far.

Both are O(n!); the swap version allocates nothing extra.

Where to record

Unlike Subsets, a partial path is not an answer — a permutation must use every element. So recording happens only at the leaf:

if (path.size() == nums.length) { record(path); return; }

That's the general pattern: record where the problem's definition of "complete" is satisfied. Subsets records at every node; permutations only at depth n; Combination Sum only when the remainder hits zero.

3. Solution Paths

Approach 1 — Backtracking with a used[] array

public List<List<Integer>> permute(int[] nums) {
    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) {                  // complete permutation
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {            // EVERY element, no start index
        if (used[i]) continue;                          // already in this permutation

        used[i] = true;  path.add(nums[i]);             // choose
        backtrack(nums, used, path, result);            // explore
        used[i] = false; path.remove(path.size() - 1);  // un-choose BOTH
    }
}

Trace — nums = [1,2,3], first branch:

• Time O(n · n!) — n! permutations, O(n) to copy each · Space O(n) for used plus O(n) depth

Counter-questions on this approach

⭐ "Why is there no start index here, when the previous two questions needed one?"

Because those produced combinations, where order doesn't matter — so [1,2] and [2,1] are the same answer, and the start index collapsed them into one path.

Here order is the answer. [1,2,3] and [2,1,3] are different permutations, so I must be able to pick a smaller index after a larger one. The loop has to scan everything.

That's the cleanest way to state the distinction: a start index exists to destroy order information. Permutations need it kept.

⭐ "Then what stops an element being reused within one permutation?"

The used[] array. The start index was doing that job implicitly for combinations — moving past an element made it unreachable. With the loop scanning everything, I need it explicit.

Note both must be undone on backtrack: used[i] = false and the path.remove. Forgetting either corrupts every sibling branch.

⭐ "Why record only at path.size() == nums.length rather than at every node like Subsets?"

Because a partial path isn't a permutation — a permutation must use every element. [1,2] is not an answer for [1,2,3].

Where you record is the problem-specific part of the template: Subsets records at every node because every prefix is a subset; Combination Sum records when the remainder hits zero; this records at full depth.

"What's the cost of the if (used[i]) continue; scan?"

At depth d, the loop scans all n entries to find the n − d unused ones. So the total work per permutation is O(n²) rather than O(n) — but it's dominated by the n! factor, so the bound stays O(n · n!). At n = 6 it's entirely irrelevant.

If it mattered, a swap-based version avoids the scan entirely.

"Would a Set be cleaner than boolean[]?"

It reads a little better but it's slower — hashing and boxing per check versus an array index. With distinct values a Set<Integer> works; with duplicates it would be wrong, since two equal values are distinct positions. The boolean[] indexes positions, which is the right thing to track.

Approach 2 — Swapping in place

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, result);
    return result;
}

private void backtrack(int[] nums, int depth, List<List<Integer>> result) {
    if (depth == nums.length) {
        List<Integer> copy = new ArrayList<>();
        for (int n : nums) copy.add(n);
        result.add(copy);
        return;
    }

    for (int i = depth; i < nums.length; i++) {
        swap(nums, depth, i);                 // choose: put nums[i] at this position
        backtrack(nums, depth + 1, result);   // explore
        swap(nums, depth, i);                 // un-choose: put it back
    }
}

private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

• Time O(n · n!) · Space O(n) depth only — no used array, no path list

Counter-questions on this approach

⭐ "There's a loop starting at depth. Isn't that a start index?"

It looks like one but it does something different. In the combination problems, start meant "only consider elements after this one", which discarded orderings. Here, nums[depth..n) is simply the set of not-yet-placed elements — the array has been partitioned into a fixed prefix and an unplaced suffix.

Every unplaced element still gets its turn at position depth, so no ordering is lost. The loop bound is bookkeeping, not a constraint.

⭐ "Why does the second swap restore the array?"

It's the un-choose. The array is shared mutable state, exactly like path in the other version. Without restoring it, the next iteration of the loop would swap from a corrupted arrangement and produce wrong permutations — and the array would be left permuted when the call returns.

Same discipline, different representation: mutate, recurse, undo.

"Does this generate permutations in a different order?"

Yes — the swap version doesn't produce lexicographic order even from a sorted input, because swapping disturbs the relative order of the unplaced suffix. The used[] version does. The problem allows any order, but it's worth knowing if sorted output were required.

"Which would you write?"

The used[] version, for clarity and because it extends directly to the duplicates case (Permutations II needs a sorted array plus a skip, which is awkward under swapping). The swap version is the one to mention if asked to avoid extra space.

Approach 3 — Insert into every position of each shorter permutation

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());

    for (int n : nums) {
        List<List<Integer>> next = new ArrayList<>();
        for (List<Integer> perm : result)
            for (int pos = 0; pos <= perm.size(); pos++) {   // every insertion point
                List<Integer> copy = new ArrayList<>(perm);
                copy.add(pos, n);
                next.add(copy);
            }
        result = next;
    }
    return result;
}

• Time O(n · n!) · Space O(n · n!) — holds all intermediate levels

Counter-questions on this approach

⭐ "No recursion. Why not prefer it?"

It materialises every intermediate level — all k! permutations of the first k elements before building the next. That's O(n!) live objects rather than O(n) of stack.

And like the iterative approaches in the previous questions, it has no place for pruning. If some permutations were invalid, this builds them all and filters afterwards; backtracking abandons them at the first bad choice.

"Why does inserting into every position give exactly n!?"

A permutation of k elements has k + 1 insertion points, so each level multiplies the count by k + 1: 1 → 2 → 6 → 24. That's the factorial, built up multiplicatively.

Comparison

4. Why the Optimal Wins

All three are O(n · n!), which is optimal — the output is that large.

The used[] backtracking wins on space against the iterative version (O(n) versus O(n!) live) and on extensibility against both: adding a constraint means adding a continue, not restructuring.

The framing worth keeping:

A start index destroys ordering — use it for combinations. Permutations need ordering kept, so the loop scans everything and a used[] array prevents reuse instead.

That one sentence is the whole difference between this question and the previous two, and it's the distinction the section is built around.

5. Java Prerequisites

The permutation template

if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    used[i] = true;  path.add(nums[i]);
    backtrack(...);
    used[i] = false; path.remove(path.size() - 1);
}

Undo everything you did. Two mutations on the way in means two on the way out.

List.add(index, element) inserts at a position, shifting the rest right — O(n).

Copying a primitive array into a list needs an explicit loop or a stream; Arrays.asList(intArray) gives a one-element List<int[]>, not a List<Integer>. A classic trap — see 02.

6. Interview Communication Guide

Clarifying questions: Are elements distinct (yes — Permutations II is the duplicate variant)? Does output order matter (no)? May I modify the input array (the swap version does)? What's the maximum n (6 — so n! is 720)?

The pitch

"There are n! permutations, so the output is factorial and that's the floor.

The structural point is that permutations need no start index — and it's worth saying why, because the previous two questions both used one.

A start index makes the loop move only forward, which forces non-decreasing index order and collapses [1,2] and [2,1] into one path. That's exactly what combinations want, because order doesn't matter there.

Here order is the answer — [1,2,3] and [2,1,3] are different permutations — so I must be able to pick a smaller index after a larger one. The loop scans every element at every level.

That means something else has to stop an element being used twice, so I keep a used[] boolean array: mark on choose, unmark on un-choose. Both undos matter — the used flag and the path.remove.

And I record only at full depth, not at every node, because a partial path isn't a permutation. Where you record is the problem-specific part of the template: Subsets records everywhere, Combination Sum when the remainder hits zero, this at depth n.

O(n · n!) time, O(n) space.

There's a swap-based variant that avoids the used array by partitioning the array into a placed prefix and an unplaced suffix. It's O(n) stack and nothing else, but it's harder to extend to the duplicates variant, so I'd write the used[] version by default."

Edge cases to volunteer:

Name [1,2]. Producing both orderings is the minimal proof that no start index is in play — a solution that accidentally kept one would return only [[1,2]].

7. Follow-Up Questions — Modified Constraints

⭐ "What if the input contained duplicates?"

Permutations II (LC 47). Sort first, then skip a value whose identical predecessor is unused at this level: if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;.

The !used[i-1] is the subtle part and differs from the subsets rule. If nums[i-1] is used, we're deeper in the same branch and this is a legitimate second copy; if it isn't used, we already tried that value at this position and this would duplicate the branch.

Worth being accurate here: inverting the condition to used[i-1] also produces the correct set — it just prunes far later. I measured the recursive calls on identical inputs:

input	unique perms	!used[i-1]	used[i-1]
[1,1,2]	3	9 calls	12 calls
[1,1,1,1,2,2]	15	55 calls	331 calls
[3,3,3,3,3,3,3]	1	8 calls	733 calls

So it's a pruning difference rather than a correctness one, and it widens sharply as duplicates dominate — 92× on the all-identical case. !used[i-1] is the one to write, but I'd describe the other as slower rather than broken.

⭐ "Generate permutations in lexicographic order."

Sort the input and use the used[] version — it emits them in lexicographic order naturally, because the loop always tries the smallest unused element first. The swap version does not, since swapping disturbs the suffix order.

"Generate the next permutation in place, not all of them."

LeetCode 31, and a completely different algorithm: scan from the right for the first descent, find the smallest element to its right that's larger, swap, then reverse the suffix. O(n) time, O(1) space — no search at all. Worth naming because "next permutation" sounds like a variation and isn't.

"Return the k-th permutation directly."

LeetCode 60. Use the factorial number system: k / (n-1)! selects the first element, then recurse on the remainder. O(n²) with no enumeration. Same idea as generating the k-th subset from a bitmask — the ordering is a numbering.

"What if n were 12?"

12! is 479 million permutations — about 23 GB just to store them. You cannot materialise the output, so you'd stream them through a callback or an Iterator, generating each on demand. The generation is still O(n) per permutation; it's only the accumulation that's impossible.

"Permutations of a string with a fixed length k?"

Change the base case to path.size() == k. That gives n!/(n−k)! results — partial permutations. One line, and a good check that the base case is understood as "the problem's definition of complete" rather than a fixed idiom.