Permutations

Given an array of distinct integers, return all possible permutations. Order does not matter.

Why this is worth learning

Positions matter here, unlike combinations. The used array tracks which input identities are already present in the current arrangement, so the next choice ranges over every unused index.

Before coding: one-minute experiment

For [1,2,3], why must the branch after prefix [2] still be allowed to choose 1, whereas combinations would prohibit moving backward?

Function signature

func Permute(nums []int) [][]int

Inputs / outputs

• nums: distinct integers.
• Return: all permutations of nums.

Example

nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints

• 1 <= len(nums) <= 8

Core idea (near-solution)

Start by filling output positions from left to right. For input [1,2,3], choosing 2 first must leave both 1 and 3 available; the increasing-start rule used for combinations would lose [2,1,3]. The future depends on which indices were chosen, not merely how many. A used array records exactly that information, while the path records their order.

Backtrack by choosing one unused element at a time.

Invariant: path is a permutation of a subset of nums with no repeats.

Algorithm (step-by-step)

1. Maintain a used boolean array.
2. DFS with path:
   • If len(path) == len(nums), record a copy.
   • Otherwise, for each index i not used:
     • Mark used, append nums[i], recurse, then backtrack.
3. Return all recorded permutations.

Correctness sketch

Before each call, path contains distinct selected input entries and used marks exactly those entries. Marking one unused index, appending its value, and recursing adds one new position without duplication. At length n, every input entry appears exactly once, so the path is a permutation. Every permutation determines a unique order of selected indices and is therefore emitted exactly once. Unmarking and popping restore both pieces of state before the next branch. The distinct-input precondition is essential: equal input values would make different index permutations produce duplicate value rows.

Trace (hand walkthrough)

Example input:
nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Walk:
- fix 1 -> [1,2,3], [1,3,2]
- fix 2 -> [2,1,3], [2,3,1]
- fix 3 -> [3,1,2], [3,2,1]

Pitfalls to avoid

• Forgetting to unmark used[i] on backtrack.
• Returning references to the same slice (must copy on output).

Debugging lens

Test result count n!, every row length n, exact input multiset, and absence of duplicate rows. Also mutate one returned row in a test to detect shared backing arrays without expecting input mutation.

Complexity

• Time: O(n * n!).
• Extra space: O(n) recursion depth (excluding output).

Implementation notes (Go)

• Copy with append([]int(nil), path...) when appending to results.

Reconstruction checkpoint

For [1,2,3], why must the branch after prefix [2] still be allowed to choose 1, whereas combinations would prohibit moving backward?

Return to Backtracking · Module quiz