LeetCode 46 Permutations - Example and Complexity Analysis

Trace [1, 2, 3].

Start with empty permutation [].

Position 0: try 1. Permutation: [1]. Position 1: try 2. Permutation: [1, 2]. Position 2: try 3. Permutation: [1, 2, 3]. Complete! Add to results. Backtrack to [1, 2]. Backtrack to [1]. Try 3. Permutation: [1, 3]. Position 2: try 2. Permutation: [1, 3, 2]. Complete! Backtrack... Position 0: try 2... continue similarly.

Generate all $n!$ permutations. Each takes $O(n)$ to copy. Total: $O(n \cdot n!)$ time. Space: $O(n)$ for recursion depth plus $O(n \cdot n!)$ for output.