Generate all permutations of distinct integers

Given a list of distinct integers, return every possible ordering of it.

Interface

Unless you agree on a different interface with the interviewer, assume:

• permutations(nums: list[int]) -> list[list[int]] — returns all n! orderings, in any order.

Example

permutations([1, 2, 3])  ->  [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
permutations([0])        ->  [[0]]
permutations([])         ->  [[]]

Constraints

• 0 <= len(nums) <= 8.
• All values are distinct.

Clarifying questions

• Does the output order matter?
• Can the input contain duplicates?
• What should an empty list return?
• Return a list, or yield the permutations one at a time?

What a strong answer covers

• Backtracking: pick an unused element for each position, recurse, undo the choice; or swap elements into place.
• Cost: n! results of length n, so O(n · n!) time and output; O(n) extra space for the recursion.
• Copying the current path when you record it, not storing the shared list.
• Tests: empty input, one element, and the count n! with no duplicates in the result.

Follow-ups

• The input may contain duplicates: return each distinct ordering once ([1, 1, 2] gives three). Sort and skip a value equal to the previous one that isn't in use.
• Generate the next permutation in lexicographic order, in place.
• Return only the k-th permutation without generating the rest.