Permutations: Backtracking With Used Array

Permutations 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]]

Intuition

A permutation is a sequence built by repeatedly picking an unused element. That single sentence defines both the state (which elements remain) and the transition (append one). A used boolean array makes that state explicit, while the swap-in-place variant encodes “unused” as “to the right of start” by physically moving chosen elements to the front. Both are DFS over the same decision tree of n! leaves, just with different bookkeeping.

Explanation with 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.

                       []
      +--------------+--------------+
    pick 1         pick 2         pick 3
     [1]            [2]            [3]
    /   \          /   \          /   \
 [1,2][1,3]     [2,1][2,3]     [3,1][3,2]
   |     |        |     |        |     |
[1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]

used[] flips on entry and flips back on return.

Code

The used-array version is the safer default. The swap-in-place variant avoids the extra array but mutates the input.

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


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

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<bool> used(nums.size(), false);
        vector<int> path;
        backtrack(nums, used, path, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used, path, result);
            path.pop_back();
            used[i] = false;
        }
    }
};

Edge Cases

• Empty array: return [[]], the single empty permutation.
• Single element: return [[x]].
• Duplicates in input: this template will produce duplicate permutations. Use the Permutations II 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 the duplicates variant, 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

• Permutations II (duplicates allowed)
• Subsets
• Combination Sum
• 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.