Permutations

Return every possible ordering of the input values.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Permutations: Fill each path position with every unused index, then pop and clear that same index before the next branch.

Input and goalReturn every possible ordering of the input values.

Initialize all indices unusedchoose() starts with path=[] and used=[F,F,F]; no permutation is complete yet.

[]active callF,F,F

inputnums = [1, 2, 3]columnspath | used indicesactioninitializeanswer[]

Recognize it

Use this pattern when every ordering is required and each input position may appear exactly once in each complete path.

Keep true

At every choose call, used[index] is true exactly when nums[index] appears in path, path length is the next output position, and returning from a branch restores both structures to their entry state.

Reuse it

When choices are reusable across sibling branches but forbidden within one path, mark before recursion and unmark after return; index-based flags also handle equal values more safely than value membership.

Pattern: Backtracking with a used list.

Simple idea: At each position, try every value that is not already in the path. Remove it after that branch finishes.

def permutations(nums: list[int]) -> list[list[int]]:
   answer: list[list[int]] = []
   path: list[int] = []
   used = [False] * len(nums)

   def choose() -> None:
      if len(path) == len(nums):
         answer.append(path.copy())
         return

      for index, num in enumerate(nums):
         if not used[index]:
            used[index] = True
            path.append(num)
            choose()
            path.pop()
            used[index] = False

   choose()
   return answer

Cost: $O(n\times n!)$ time and $O(n)$ working space.