Permutations

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

Before you code

Unlike subsets, every position can take any unused element, so there is no start index. The search tree has n! leaves.

Hints

1. Keep a used array of booleans. At each level, loop over every index that isn't used, choose it, recurse and unchoose it.
2. Record the path when its length is n.
3. Alternative: build permutations in place by swapping nums[depth] with each nums[i] for i >= depth, recursing, and swapping back.

Production & complexity notes

When solving Permutations on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.

What it practices

The choose, explore, unchoose pattern and pruning, from Backtracking basics.