Problem Statement

Permutations

You are given an array called nums that holds distinct integers (distinct means no number repeats). Your job is to return every possible ordering of those numbers. An ordering, also called a permutation, is just one way of lining up all the numbers. For example, [1,2,3] and [2,1,3] use the same numbers but in a different order, so they count as two different permutations. You can return the answers in any order.

mediumBacktrackingBacktrackingTime: O(n * n!) · Space: O(n)

Signals to notice

generate all possible orderingseach element used exactly oncen! results

Brute force first

Not applicable — generating all permutations IS the problem. Output size is n!, which is unavoidable. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Backtracking: pick each unused element for the current position, recurse for remaining positions, then unpick. — one recursive call per permutation. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `nums=[1,2,3]`

backtrack(current=[], remaining=[1,2,3]) -> not empty, start loop
pick 1: current=[1], recurse remaining=[2,3] -> pick 2: current=[1,2], remaining=[3] -> pick 3: current=[1,2,3], remaining=[] EMPTY -> result=[[1,2,3]], pop back to [1,2]
back at current=[1], pick 3: current=[1,3], remaining=[2] -> pick 2: current=[1,3,2], remaining=[] -> result+=[1,3,2]; pop back to []
pick 2: current=[2], remaining=[1,3] -> yields [2,1,3] then [2,3,1]; pop back to []
pick 3: current=[3], remaining=[1,2] -> yields [3,1,2] then [3,2,1]; pop back to []
loop over remaining exhausted -> return result = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

What must stay true

At each position, try every element that hasn't been used yet. After exploring all choices for deeper positions, undo the choice (backtrack) and try the next element. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

function backtrack(current, remaining):
  if remaining is empty: add copy of current to result; return
  for i in 0..len(remaining)-1:
    current.push(remaining[i])
    backtrack(current, remaining without index i)
    current.pop()

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not properly tracking which elements are used — a boolean array or set prevents reusing elements. Swapping elements in-place is an elegant alternative that avoids extra tracking. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Backtracking Pattern