LeetCode 46 — Permutations (Backtracking)

What does it solve?

Given an array nums of distinct integers, return all possible permutations (in any order).

Example: nums=[1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] — exactly 3! = 6 permutations.

Backtracking template

// path = current permutation being built
backtrack(path, used):
  if len(path) == n:
    result.add(path.copy()) // leaf!
    return
  for num in nums:
    if used[num]: continue
    choose num → recurse → unchoose num

💡 Key insight: Think of it as a decision tree — at each level you choose one unused number for the current position, recurse deeper, then undo that choice (backtrack) to try the next option. The tree has depth n and each leaf (at depth n) is one complete permutation. The "used" array prevents picking the same number twice in one path — this is what separates permutations from combinations with repetition.

Complexity

Time

O(n·n!)

n! permutations total, each takes O(n) to copy into the result.

Space

O(n)

Recursion depth + used array + path array, excluding the output storage.

Examples & edge cases

Live animation — Backtracking Decision Tree

In current path Trying this choice Backtrack (undo) Complete permutation found

⏸ Waiting to start

Current path (permutation under construction)

Available numbers

Recursion tree — choices at each depth scroll to see full tree

Permutations found so far

Step — of —

Depth

—

of n

Calls made

recursive calls

Backtracks

undos

Found

of n! total

Select an example and press Play to begin.

✓ All found!

Speed Medium

Step-by-step table

Step	Depth	Action	Number	Path	Note

C++ implementation

permutations.cpp

#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<int>& nums, vector<int>& path,
               vector<bool>& used, vector<vector<int>>& result) {
    // Base case: path is complete — record it
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }

    // Try every unused number for the next position
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;       // skip already-used numbers

        // Choose
        used[i] = true;
        path.push_back(nums[i]);

        // Explore
        backtrack(nums, path, used, result);

        // Un-choose (backtrack)
        path.pop_back();
        used[i] = false;
    }
}

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

int main() {
    vector<int> nums = {1, 2, 3};
    auto result = permute(nums);
    // 6 permutations printed
    for (auto& p : result) {
        for (int x : p) cout << x << " ";
        cout << "\n";
    }
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars