Permutations

Problem

Given an array of distinct integers, return all possible permutations in any order.

Approach

Backtrack by fixing one position at a time. For position first, swap each remaining number into that slot, recurse to fill the rest, and then swap back to restore the array.

Swapping in place avoids a separate used array. A copy of the array is recorded each time every position is filled.

Solution

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []

        def backtrack(first: int) -> None:
            if first == len(nums):
                result.append(nums[:])
                return
            for i in range(first, len(nums)):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]

        backtrack(0)
        return result

Complexity

• Time: O(n · n!): n! permutations, each copied in O(n).
• Space: O(n) for the recursion, excluding the output.

Edge cases

• A single number returns one permutation.
• With duplicate numbers this would repeat permutations; that is the separate Permutations II problem.