Permutations

Problem

Test harnesses generate all orderings of a fixed parameter list to verify that a function's behavior is order-independent. Given an array of distinct integers, return all possible permutations. Every element must appear exactly once in each permutation, and all n! orderings must be returned.

Input: [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 
Input: [0, 1]
Output: [[0,1],[1,0]]

Solution

Approach: Backtracking with a used boolean array, looping from index 0 at every level.

Because order matters, there is no start index - any element not yet in the current path is a candidate for the next position, even one that sits earlier in the array. The used array of booleans tracks membership: the loop runs over all indices, skips any where used[index] is True, and for the rest applies choose-explore-unchoose. The choose step is two mutations - used[index] = True and path.append(nums[index]) - and the unchoose step must undo both: path.pop() then used[index] = False. Resetting the flag is as important as the pop, because the used array is shared across all sibling branches; leaving it True would hide that element from every later ordering. A path is recorded only at a leaf, when len(path) == len(nums), since a permutation must place every element. Trace [1, 2]: the loop picks index 0 (1), recurses, picks index 1 (2) for [1, 2], unwinds clearing both flags, then from the root picks index 1 (2) first and index 0 (1) to get [2, 1] - 2! = 2 orderings.

Edge cases: A single element produces one permutation. The distinct-element assumption matters - duplicate inputs would yield repeated permutations here (Permutations II adds a sorted same-depth skip to fix that).

Complexity: O(n * n!) time, O(n) space - n! leaves each copied in O(n); the recursion stack, path, and used array are all length n (output excluded).