Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Permutations
• Main tags: Array, Backtracking

What the problem is really asking

The input contains distinct integers, and the task is to return every possible ordering of those integers.

That means the algorithm is not trying to find one best answer. It is trying to systematically explore a decision tree where:

• the first slot can take any number
• the second slot can take any remaining number
• the third slot can take any still-unused number

Once that perspective is clear, the problem becomes a textbook backtracking problem.

How to derive the right solution

The cleanest way to think about permutations is to build the answer from left to right.

Suppose the current partial permutation is [2, 1]. The next step is simple: try every number that has not been used yet. If 3 is unused, extend to [2, 1, 3]. If 4 is unused, extend to [2, 1, 4]. Each choice creates a smaller subproblem with one fewer available number.

That naturally leads to this pattern:

1. Keep a partial permutation.
2. Keep track of which numbers are already used.
3. When the partial permutation reaches length n, record a copy.
4. After exploring one choice, undo it so the next choice starts from a clean state.

That “choose, explore, undo” rhythm is exactly what backtracking is.

Optimal solution

The standard interview solution uses depth-first search with backtracking:

• iterate through every index in nums
• skip values that are already used in the current path
• append one unused value
• recurse to fill the next position
• pop the value and mark it unused again

This is asymptotically optimal for generating all permutations because the output itself has size n!, and each completed permutation has length n.

There is also an equally good in-place variant that swaps the current position with every later position. It avoids a separate used array, but many candidates find the explicit used version easier to reason about in an interview. Both approaches run in O(n * n!) time.

Why the backtracking state is enough

The recursion only needs two pieces of state:

• current_permutation: what has been chosen so far
• used_indices: which numbers are already in that partial answer

Nothing else matters. Once those two structures are correct, the remaining work is just “try every unused choice.” That is why the implementation stays compact even though the search space is large.

Complexity

• Time: O(n * n!)
• Extra space: O(n) auxiliary space for the recursion stack, current permutation, and used markers, not counting the output
• Output space: O(n * n!)

The n! term is unavoidable because the problem asks for every permutation.

Python solution

from typing import Sequence


class PermutationGenerator:
    """Generate every permutation of a sequence of distinct integers."""

    def generate(self, numbers: Sequence[int]) -> list[list[int]]:
        total_numbers = len(numbers)
        used_indices = [False] * total_numbers
        current_permutation: list[int] = []
        all_permutations: list[list[int]] = []

        self._build_permutations(
            numbers=numbers,
            used_indices=used_indices,
            current_permutation=current_permutation,
            all_permutations=all_permutations,
        )

        return all_permutations

    def _build_permutations(
        self,
        numbers: Sequence[int],
        used_indices: list[bool],
        current_permutation: list[int],
        all_permutations: list[list[int]],
    ) -> None:
        if len(current_permutation) == len(numbers):
            all_permutations.append(current_permutation.copy())
            return

        for index, value in enumerate(numbers):
            if used_indices[index]:
                continue

            # Choose one unused value for the next position.
            used_indices[index] = True
            current_permutation.append(value)

            self._build_permutations(
                numbers=numbers,
                used_indices=used_indices,
                current_permutation=current_permutation,
                all_permutations=all_permutations,
            )

            # Undo the choice before trying the next candidate.
            current_permutation.pop()
            used_indices[index] = False


def permute(numbers: Sequence[int]) -> list[list[int]]:
    generator = PermutationGenerator()
    return generator.generate(numbers)

This implementation is easy to debug because the state transitions are explicit. At any recursion level, the partial answer is the current path, and the boolean array tells exactly which indices are unavailable.

Interview follow-ups

What if the input can contain duplicate values?

Then the plain version above will generate duplicate permutations, because choosing the first 1 and the second 1 may lead to the same final ordering. A standard fix is to sort the array first and skip a duplicate value when it matches the previous value and the previous value has not been used in the current recursion level. That rule ensures that equal numbers are chosen in a consistent order, so each unique permutation is produced once. The time complexity is still proportional to the number of valid permutations generated, but the duplicate-skipping logic prevents wasted branches.

What if the interviewer wants permutations streamed one at a time instead of stored in a list?

The same backtracking structure still works, but instead of appending to all_permutations, the recursive function yields each finished permutation immediately. This changes the interface from “return a full list” to “produce results lazily,” which is useful when the caller wants to process permutations incrementally or when the full output would be too large to keep in memory. The search still takes O(n * n!) total time in the worst case, but the extra storage beyond the current path drops to the recursion state instead of growing with all answers.

How would you return the k-th permutation without generating all permutations?

That becomes a different problem. Instead of backtracking through the entire tree, use factorial block sizes to decide which digit belongs in each position. For example, with n numbers, each first choice owns (n - 1)! permutations. That lets the algorithm jump directly to the correct block, remove that element from the candidate pool, and continue on the suffix. This approach is much faster than generating every permutation when only one ranked answer is needed, typically around O(n^2) time with a simple list-based implementation because removing from the middle of a list costs linear time.

Takeaway

Permutations looks large, but the logic is simple once the problem is seen as “fill the next slot with every unused number.” Backtracking fits naturally because every recursive call represents a partial answer, and undoing the last choice cleanly restores the state for the next branch.