# 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

```python
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

> **[Open interactive visualization](https://tracelit.dev/app?trace=0046_permutations)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0046_permutations) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*