You’re in a coding interview. The interviewer gives you [1, 2, 3] and asks you to generate all permutations. You recognize it’s backtracking, reach for the same start-index pattern you used for Combination Sum, and immediately start missing valid outputs. [2, 1, 3] never appears because your start index won’t let you look backward. The interviewer watches you debug for two minutes before asking: “What’s different about permutations versus combinations?”

This walkthrough covers how that conversation should go instead: why permutations require a fundamentally different tracking mechanism than combinations, how the used-array pattern works, and the swap-based alternative that eliminates extra space.

---

The Problem

Given an array nums of distinct integers, return all possible permutations. You may return the answer in any order.

(LeetCode #46)

Example 1

Input nums = [1, 2, 3]

Output [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Example 2

Input nums = [0, 1]

Output [[0,1], [1,0]]

In Example 1, there are 3! = 6 permutations of three distinct elements: every possible ordering appears exactly once. Unlike combinations, order matters here: [1, 2, 3] and [2, 1, 3] are different permutations. Every element must appear in every permutation exactly once.

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

Permutations is a backtracking problem where the branching logic differs subtly but importantly from combination problems. Interviewers use it to check whether you understand the distinction.

Skill	What Interviewers Observe
Backtracking fluency	Can you implement choose/explore/unchoose cleanly without prompting?
Permutation vs combination distinction	Do you know why you can’t use a start index here, and what you use instead?
Used-element tracking	Do you track which elements are already in the current permutation, and how?
Base case clarity	Do you correctly identify when a permutation is complete?
Communication	Can you explain the decision tree and pruning logic before writing code?

---

Step 1: Clarifying Questions

1. Are all elements in nums distinct? The standard problem guarantees distinct integers. If duplicates were allowed (LeetCode #47), you’d need a sorting step and a same-level skip check. Confirming distinctness keeps you on the simpler version.

2. Can nums be empty? An empty array has exactly one permutation: the empty permutation [[]]. Confirming this shapes your base case.

3. Does the order of permutations in the output matter? No, the problem says “any order.” You don’t need to sort your results.

4. What’s the maximum length of nums? At most 8 elements. 8! = 40,320 permutations is entirely manageable, confirming an exponential algorithm is acceptable.

5. Are we returning indices or the actual values? The values themselves, not indices.

---

Step 2: A First (Non-Optimal) Idea

The most obvious approach uses Python’s itertools.permutations:

from itertools import permutations

def permute_builtin(nums):
    return [list(p) for p in permutations(nums)]

This is correct but completely sidesteps what the interviewer wants to see. It doesn’t demonstrate backtracking and gives the interviewer nothing to evaluate.

A slightly more thoughtful approach: at each step, pick an unused element, recurse with the remaining elements:

def permute_naive(nums):
    if len(nums) == 0:
        return [[]]
    results = []
    for i, num in enumerate(nums):
        rest = nums[:i] + nums[i+1:]
        for perm in permute_naive(rest):
            results.append([num] + perm)
    return results

This is correct and O(n! x n) in time, but it creates new list slices at every recursive level, O(n) extra space per call. It also doesn’t follow the classic backtracking pattern (in-place mutation + undo), which is what interviewers want to see.

---

Step 3: The Key Insight

In combinations, you move forward through candidates and never look back. In permutations, every unused element is a valid choice at every position. You can’t use a start index because [2, 1, 3] and [1, 2, 3] are both valid. Instead, track which elements are already placed using a used boolean array. At each recursive level, iterate over all elements and skip the ones already used.

The two standard approaches:

Approach 1: used boolean array. Keep a used[i] flag for each index. At each recursive level, iterate over all elements and skip the ones already marked.

Approach 2: In-place swapping. Swap elements into the “current position” one at a time, recurse on the remaining suffix, then swap back. No extra space needed for tracking.

Both are O(n! x n) in time. The used array approach is easier to reason about and explain. We’ll implement both, but lead with the used array version.

---

Step 4: Optimal Strategy

1. Initialize an empty results list and a used boolean array of length n, all False.
2. Define backtrack(current_perm).
3. Base case: If len(current_perm) == len(nums), append a copy of current_perm to results and return.
4. Recursive step: Loop through all indices i in nums:
   • If used[i] is True, skip.
   • Mark used[i] = True, append nums[i] to current_perm.
   • Recurse: backtrack(current_perm).
   • Undo: mark used[i] = False, pop nums[i] from current_perm.
5. Call backtrack([]) to start.

---

Python Implementation

def permute(nums: list[int]) -> list[list[int]]:
    results = []
    used = [False] * len(nums)  # Tracks which elements are in the current permutation

    def backtrack(current_perm: list[int]):
        # Base case: current permutation is complete
        if len(current_perm) == len(nums):
            results.append(list(current_perm))  # Append a copy, not the reference
            return

        for i in range(len(nums)):
            if used[i]:
                continue  # Skip elements already in this permutation

            # Choose
            used[i] = True
            current_perm.append(nums[i])

            # Explore
            backtrack(current_perm)

            # Unchoose
            current_perm.pop()
            used[i] = False

    backtrack([])
    return results

Let’s trace nums = [1, 2, 3]:

backtrack([])
├── pick 1 → backtrack([1])
│   ├── pick 2 → backtrack([1,2])
│   │   └── pick 3 → backtrack([1,2,3]) → ✓ append [1,2,3]
│   └── pick 3 → backtrack([1,3])
│       └── pick 2 → backtrack([1,3,2]) → ✓ append [1,3,2]
├── pick 2 → backtrack([2])
│   ├── pick 1 → backtrack([2,1])
│   │   └── pick 3 → backtrack([2,1,3]) → ✓ append [2,1,3]
│   └── pick 3 → backtrack([2,3])
│       └── pick 1 → backtrack([2,3,1]) → ✓ append [2,3,1]
└── pick 3 → backtrack([3])
    ├── pick 1 → backtrack([3,1])
    │   └── pick 2 → backtrack([3,1,2]) → ✓ append [3,1,2]
    └── pick 2 → backtrack([3,2])
        └── pick 1 → backtrack([3,2,1]) → ✓ append [3,2,1]

All 3! = 6 permutations collected. The used flags ensure no element appears twice in any path from root to leaf.

Bonus: In-Place Swap Approach

def permute_swap(nums: list[int]) -> list[list[int]]:
    results = []

    def backtrack(start: int):
        if start == len(nums):
            results.append(list(nums))
            return

        for i in range(start, len(nums)):
            # Swap nums[i] into the current position
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            # Swap back to restore original order
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return results

This approach treats nums itself as the “current permutation” by swapping elements into place. It uses O(1) extra space beyond the output and call stack. The tradeoff: it’s slightly harder to explain verbally and easier to get the swap indices wrong.

---

Time & Space Complexity

Aspect	Complexity	Explanation
Time	O(n! x n)	n! permutations, copying each takes O(n)
Space (call stack)	O(n)	Recursion depth is exactly n
Space (used array)	O(n)	One boolean per element
Space (output)	O(n! x n)	Storing all permutations

Time: O(n! x n) is unavoidable. You can’t enumerate n! permutations faster than O(n!), and each copy costs O(n). The backtracking itself does no redundant work; every leaf in the decision tree corresponds to exactly one permutation.

Space: The recursion depth is exactly n (one level per element placed).

---

Common Interview Mistakes

1. Using a start index instead of a used array. This is the combination-problem habit bleeding into a permutation problem. A start index prevents you from placing 1 after 2: you’d miss [2, 1, 3] entirely. Permutations require every unused element to be available at every position.

2. Appending current_perm directly instead of a copy. results.append(current_perm) stores a reference. As backtracking modifies the list, every stored result changes with it. You’ll end up with a list of identical empty lists. Always append list(current_perm).

3. Forgetting to reset used[i] after the recursive call. The undo step must reset both the list (pop) and the flag (used[i] = False). Forgetting the flag reset means once an element is used in one branch, it stays marked used for all subsequent branches.

4. Checking len(current_perm) == n with the wrong n. If you shadow n somewhere or use len(nums) inconsistently, the base case can silently trigger too early or too late.

5. Getting the swap indices wrong in the swap approach. You swap nums[start] with nums[i], not nums[i] with nums[i+1]. Confusing the “current position” (start) with the “candidate” (i) produces wrong or duplicate permutations.

6. Not drawing the decision tree before coding. Permutations have a clean, symmetric decision tree that’s easy to sketch. Spending 60 seconds drawing the first two levels for [1, 2, 3] prevents most bugs.

7. Treating this problem like Combination Sum. The two problems look structurally similar but differ in a key way: combinations avoid revisiting earlier candidates using a start index; permutations need to revisit all elements using a used-tracking mechanism.

---

What a Strong Candidate Sounds Like

“Unlike combinations, where I move forward through candidates to avoid duplicate orderings, permutations require me to consider every unused element at every position. So instead of a start index, I’ll use a used boolean array to track which elements are already in the current permutation. At each level of recursion, I iterate over all elements, skip the ones marked used, add the current element, recurse, then undo both the append and the flag. The base case is when the current permutation has the same length as nums. At that point, I’ve placed every element exactly once, so I record a copy. The decision tree has n branches at the first level, n-1 at the second, and so on, giving n! leaves total. Let me draw the first two levels before I code it.”

This response shows: the candidate understands the structural difference from combinations; they identified the used-array mechanism before coding; they can predict the output size from the decision tree.

---

Example Interview Dialogue

Interviewer: What’s the difference between how you solve this versus Combination Sum?

Candidate: The core difference is how we avoid generating duplicates. In Combination Sum, I pass a start index so each recursive call only considers candidates at or after the current position, so [2, 3] and [3, 2] don’t both get generated. But in Permutations, [1, 2, 3] and [2, 1, 3] are both valid and distinct outputs. So I can’t use a start index. I use a used array instead to skip only the elements already placed in the current permutation.

Interviewer: How would you handle duplicates in the input, like nums = [1, 1, 2]?

Candidate: That’s Permutations II. I sort nums first so duplicates are adjacent, then add a check: if i > 0 and nums[i] == nums[i-1] and used[i-1] is False, skip nums[i]. The used[i-1] == False condition ensures I skip a duplicate only when the previous identical element wasn’t used in the current path, which would mean it was used in a sibling branch, generating the same permutation.

Interviewer: What if nums has 12 elements?

Candidate: 12! is about 479 million permutations, each of length 12. Storing them all would require billions of integers. In practice I’d question whether enumerating all permutations is actually needed, or whether you can solve the underlying problem without materializing all of them, for example using next-permutation iteration or a lazy generator.

---

Related Problems to Practice

Permutations is the second core backtracking problem after Combination Sum. These problems all build on the same choose/explore/unchoose pattern:

• Permutations II (LeetCode #47). Same problem with duplicate elements. Adds a same-level skip check.
• Combination Sum (LeetCode #39). Canonical combination backtracking. Contrasts cleanly with permutation tracking.
• Letter Case Permutation (LeetCode #784). Lighter backtracking problem. Good warm-up for building permutation intuition.
• Next Permutation (LeetCode #31). Generates the lexicographically next permutation in O(n). A useful complement.
• Subsets (LeetCode #78). Pure backtracking to enumerate all subsets. The simplest decision tree.

---

Practice This in a Mock Interview

Reading this explanation gives you the decision tree model, the used-array pattern, and a clear mental picture of how backtracking unwinds. But the execution details: resetting both the list and the flag, appending a copy not a reference, knowing exactly when the base case fires, are the kind of things that quietly break under interview pressure.

The difference between candidates who pass and candidates who don’t often isn’t conceptual understanding. It’s clean execution of a pattern they’ve practiced enough times that the undo step is automatic.

Start a mock interview for Permutations on Intervu.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code