LeetCode Permutations: Backtracking With Used Array

Permutations (LeetCode 46, Medium) is the second backtracking problem every candidate should master. Two clean approaches both work; understanding the trade-offs is what interviewers really probe.

The Problem

Given an array nums of distinct integers, return all possible permutations.

Example:

• Input: nums = [1, 2, 3]
• Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Brute Force

Built-in itertools.permutations works but defeats the purpose. Generating all subsets and filtering down to those of length n is even worse.

Optimal Solution

Backtracking with a used array.

def permute(nums):
    result = []
    used = [False] * len(nums)
    path = []

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

The swap-in-place variant avoids the extra array:

def permute_swap(nums):
    result = []
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack(0)
    return result

Both produce all n! permutations.

Walk Through an Example

nums = [1, 2, 3] with the used-array version.

• path [], no used. Pick 1, path [1], used [T,F,F].
  • Pick 2, path [1,2]. Pick 3, path [1,2,3]. Record. Backtrack.
  • Pick 3, path [1,3]. Pick 2, path [1,3,2]. Record.
• Backtrack to root. Pick 2, then 1, 3 and 3, 1.
• Pick 3, then 1, 2 and 2, 1.

Six permutations total.

Edge Cases

• Empty array: return [[]], the single empty permutation.
• Single element: return [[x]].
• Duplicates in input: this template will produce duplicate permutations. Use LeetCode 47’s template (sort + skip duplicates at the same depth) for that case.
• Large n: output is n!, so n above 10 already produces millions of results; that’s a problem constraint, not your code’s fault.

Complexity Analysis

• Time: O(n * n!). There are n! permutations, each of length n.
• Space: O(n) recursion depth, plus output size.

The swap-in-place variant saves O(n) on the used array but mutates the input.

How to Explain It in an Interview

State both approaches up front. Explain why the used-array version is clearer to maintain and reason about; the swap version is more memory-efficient but harder to extend (for LeetCode 47, you’ll prefer the used-array variant with a duplicate skip rule). Walk through the first two branches and show that you increment and decrement the used flag and path symmetrically. Mention the O(n!) bound and that this is the theoretical lower bound for enumeration.

Related Problems

• LeetCode 47 Permutations II (duplicates allowed)
• LeetCode 78 Subsets
• LeetCode 39 Combination Sum
• LeetCode 31 Next Permutation

Wrap up

Permutations is the second of the “big three” backtracking warmups along with Subsets and Combination Sum. Pick one template (used-array is generally safer) and use it consistently across permutation variants. The discipline of symmetric push/pop and flag toggling pays dividends on every harder backtracking problem you meet.