Permutations

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

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)

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

• Invariant: path is a permutation of a subset of nums with no repeats.
• Each recursive step extends a valid partial solution.
• Backtracking explores all possible choices without duplication.
• Thus every valid solution is found and recorded.

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).

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.