Generate all permutations of a list of distinct integers using backtracking.
At each recursion level, swap one of the remaining (unused) elements into the current position, recurse to fill the rest, then swap back to restore the state. Alternatively, track a 'used' set and build the permutation in a separate path list. The result is all n! orderings.
How to think about it
Recognise the pattern
The signal is “every ordering” or “arrange all elements.” Unlike subsets (where you pick a subset and order doesn’t matter), permutations care about sequence. The backtracking structure is the same — build incrementally, undo, try the next — but instead of picking the next index forward (to avoid re-using earlier elements), you pick any element that hasn’t been placed yet.
Build the approach step by step
Brute force with itertools.permutations gives you the answer immediately, but interviewers want to see the construction.
The backtracking approach using a used array:
At each recursive call you have a partially built path. Loop over all indices; if used[i] is False, add nums[i] to path, mark it used, recurse, then undo both actions (backtrack). When path is full (length == n), record it.
Recursion tree for [1,2,3] (first level only):
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]Complexity
- Time — O(n × n!): there are n! permutations; recording each costs O(n).
- Space — O(n): the
pathlist andusedarray are both length n; recursion depth is n. Output O(n × n!) is unavoidable.