LeetCode 46: Permutations — Step-by-Step Visual Trace

Medium — Backtracking | Array | Recursion

The Problem

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

Approach

Uses backtracking with in-place swapping to generate permutations. At each position, we try placing each remaining element, recursively generate permutations for the rest, then backtrack by swapping elements back to their original positions.

Time: O(n! × n) · Space: O(n)

Code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start == len(nums) - 1:
                permutations.append(nums[:])  # Append a copy of the current permutation

            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]  # Swap elements
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]  # Backtrack

        permutations = []
        backtrack(0)
        return permutations

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments