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

#leetcode #python #algorithms

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