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.

Example 1:

Input: [-1, 4, 7]
Output: [[-1,4,7],[-1,7,4],[4,-1,7],[4,7,-1],[7,-1,4],[7,4,-1]]

Example 2:

Input: [5]
Output: [[5]]

Constraints:

• 1 <= nums.length <= 6
• -50 <= nums[i] <= 50
• All elements of nums are unique.

Solution Breakdown

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, 4]: the loop picks index 0 (-1), recurses, picks index 1 (4) for [-1, 4], unwinds clearing both flags, then from the root picks index 1 (4) first and index 0 (-1) to get [4, -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).