Permutations

Fix the element at index i by swapping in each candidate from the remaining suffix, recurse on i + 1, then swap back. This avoids a separate “used” structure but mutates the input array during recursion.

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

        def backtrack(i):
            if i == len(nums):
                result.append(nums[:])
                return
            for j in range(i, len(nums)):
                nums[i], nums[j] = nums[j], nums[i]
                backtrack(i + 1)
                nums[i], nums[j] = nums[j], nums[i]  # undo the swap

        backtrack(0)
        return result

Same O(n · n!) time and O(n) recursion depth as the approach below — this is really a style choice (swap vs. explicit used-set), not a performance win. It is slightly less intuitive to trace since the array itself changes shape mid-recursion.

Build a path one slot at a time. At each step, try every number not already in path (tracked via a used array), append it, recurse, then remove it. A permutation is complete once path reaches length n.

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = []
        path = []
        used = [False] * n

        def backtrack():
            if len(path) == n:
                result.append(path[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return result

Tracing nums = [1,2,3] — the decision tree branches over every unused number at each depth, so the branching factor shrinks from 3 to 2 to 1 as we go deeper:

Complexity: there are n! complete permutations, and building each one costs O(n) (one append per level plus the final copy) → O(n · n!) time. The used array and path/recursion depth are all O(n) → O(n) auxiliary space.