Permutations LeetCode Solution: Backtracking Template for #46

If there is one problem that teaches you backtracking from the ground up, it is Permutations (#46). This problem strips away every distraction — no constraints to prune, no duplicates to handle, no target sum to track. What remains is the backtracking skeleton in its cleanest form: choose an element, explore recursively, then unchoose.

Permutations LeetCode (#46) is one of the most frequently asked problems at Google, Meta, Amazon, and Microsoft. Interviewers love it because your solution reveals whether you truly understand recursive state management or are just pattern-matching from memorized code. Once you internalize this template, problems like Subsets (#78), Combination Sum (#39), and Letter Combinations of a Phone Number (#17) become variations of the same idea.

In this walkthrough, you will learn the core backtracking template, see two implementation approaches, walk through a visual decision tree, and understand exactly how this single problem unlocks an entire family of recursive exploration problems.

Given an array of distinct integers, return all possible permutations. You can return the answer in any order. For example, given [1, 2, 3], the output should be all six arrangements: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

The key word is "all." You are not searching for a single valid arrangement or an optimal one — you need every possible ordering. This is what makes backtracking the natural fit. Unlike greedy algorithms that make one choice and move on, backtracking systematically explores every branch and backtracks when a branch is complete.

Order matters in permutations. This distinguishes them from combinations, where [1,2] and [2,1] are the same. In permutations, [1,2] and [2,1] are two distinct results. For n distinct elements, there are exactly n! (n factorial) permutations. With 3 elements you get 6, with 4 you get 24, and with 6 you get 720.

Every backtracking problem follows the same three-step loop: choose, explore, unchoose. For permutations, "choose" means adding an unused element to your current path. "Explore" means recursing with the updated path. "Unchoose" means removing that element from the path so the next iteration can try a different element in the same position.

The base case is simple: when your current path has the same length as the input array, you have a complete permutation. Add a copy of the path to your results and return. The recursive case iterates over all elements, skips any that are already in the current path, and recurses for each unused element.

Here is the template in plain English. Start with an empty path and empty result list. For each element in the array: if the element is not already used, add it to the path, recurse, then remove it from the path. When the path length equals n, copy the path into results. That is the entire algorithm.

There are two standard ways to implement generate permutations with backtracking. The visited array approach uses a boolean array to track which elements are currently in the path. For each recursive call, you loop through all elements, skip those marked as visited, mark the current one as visited, recurse, then unmark it. This is the most intuitive version and the one interviewers expect first.

The swap-based approach is more space-efficient. Instead of maintaining a separate path and visited array, you swap elements in-place. At recursion depth i, you swap nums[i] with each element from index i to n-1, recurse with depth i+1, then swap back. When i equals n, the array itself is a complete permutation. This avoids the O(n) extra space for the visited array but can be harder to reason about.

Both approaches produce the same result with O(n!) time complexity — you cannot do better because there are n! permutations to generate. The visited array uses O(n) auxiliary space for the boolean array plus O(n) for the current path. The swap approach uses O(1) auxiliary space beyond the recursion stack. In interviews, start with the visited approach for clarity, then mention the swap optimization if asked.

Let us trace through the backtracking for [1, 2, 3] to see all permutations generated step by step. The decision tree starts at the root with an empty path. At level one, you have three choices: pick 1, pick 2, or pick 3. Each choice creates a branch.

Following the first branch: you pick 1, leaving 2 and 3 unused. At level two, you pick 2, leaving only 3. At level three, you pick 3, path is [1,2,3] — that is your first permutation. Backtrack: remove 3, remove 2. Now at level two again, pick 3 instead, then pick 2. Path is [1,3,2] — second permutation. Backtrack all the way to level one.

The second branch starts with 2. From there, pick 1 then 3 to get [2,1,3], or pick 3 then 1 to get [2,3,1]. The third branch starts with 3 and produces [3,1,2] and [3,2,1]. In total, 3 branches at level one, 2 at level two, 1 at level three: 3 x 2 x 1 = 6 permutations.

This tree structure is the mental model for all backtracking problems. For subsets, you add a "skip" branch at each level. For combination sum, you allow reuse. For N-Queens, you prune invalid branches. The tree is always there — the only difference is which branches you keep and which you cut.

The edge cases for permutations are straightforward but worth mentioning. A single element [5] produces exactly one permutation: [[5]]. Two elements [1,2] produce two permutations: [[1,2], [2,1]]. An empty array produces one permutation: the empty arrangement [[]]. These base cases should be handled naturally by your template without special-casing.

The most important extension is Permutations II (#47), which allows duplicate elements. For example, [1,1,2] should produce [[1,1,2], [1,2,1], [2,1,1]] — only three permutations, not six. The fix is to sort the array first, then skip an element if it equals the previous element and the previous element was not used in the current recursion level. This duplicate-skipping logic is the only addition to the template.

Other extensions include Next Permutation (#31), which asks for the lexicographically next arrangement without generating all of them, and Permutation Sequence (#60), which asks for the k-th permutation directly. These are different algorithms entirely — they use mathematical reasoning rather than backtracking. But mastering #46 first gives you the intuition to understand why those shortcuts work.

Permutations (#46) is not just another problem to check off your list — it is the foundation for an entire category of interview questions. The choose-explore-unchoose template you learn here is the exact same skeleton used in Subsets (#78), Combination Sum (#39), Letter Combinations of a Phone Number (#17), Palindrome Partitioning (#131), and N-Queens (#51). The only differences are the branching rules and pruning conditions.

When you encounter a new backtracking problem, ask yourself three questions. First, what are my choices at each step? For permutations, it is any unused element. For subsets, it is include or exclude. For combination sum, it is pick any candidate with remaining budget. Second, when do I stop? For permutations, when the path is full. For subsets, at every node. Third, when do I prune? For permutations, never — there are no invalid partial states. For N-Queens, when a queen conflicts.

Practice the permutations backtracking template until you can write it from memory in under two minutes. Then move to Subsets and Combination Sum. Once you can solve all three without looking anything up, you have internalized the pattern. YeetCode flashcards are built around exactly this kind of spaced repetition — drilling the template so it becomes second nature before your interview.