Permutations LeetCode Solution (Medium) (2026)

Approach Summary

Swap elements to place each number at index 0 recursively, or use a used[] array and add unused elements at each step.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

Generate permutations by deciding, at each position, which unused element goes there. Use a visited boolean array to track which elements are already in the current path. The recursive helper appends an unused element, recurses, then removes it — the choose/explore/unchoose skeleton. When the path length equals the array length, record a copy. Since all elements are distinct, the visited-array guard is sufficient and no duplicate handling is needed. The recursion tree has n! leaves — every permutation appears exactly once. An alternative swaps elements in place (no extra array) but is slightly harder to reason about; the visited-array version is the clearest. The same skeleton with different guards produces combinations and subsets.

There are n! permutations, each costing O(n) to build and copy — O(n × n!) time. The recursion depth is n and the path holds n elements — O(n) space.

Solution Code

Solution

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

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.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, res);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

vector<vector<int>> permute(const vector<int>& nums) {
    vector<vector<int>> res;
    vector<bool> used(nums.size(), false);
    vector<int> path;
    function<void()> backtrack = [&]() {
        if (path.size() == nums.size()) {
            res.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();
            path.pop_back();
            used[i] = false;
        }
    };
    backtrack();
    return res;
}

def permute(nums: list[int]) -> list[list[int]]:
    res = []
    used = [False] * len(nums)

    def backtrack(path: list[int]) -> None:
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, n in enumerate(nums):
            if not used[i]:
                used[i] = True
                path.append(n)
                backtrack(path)
                path.pop()
                used[i] = False

    backtrack([])
    return res

function permute(nums) {
  const res = [];
  const used = new Array(nums.length).fill(false);
  const path = [];
  function backtrack() {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  }
  backtrack();
  return res;
}

Edge Cases to Watch

Empty array — return [[]]
Single element — one permutation
Repeated values — not in this problem; Permutations II adds a sort-and-skip guard

Algorithmic Pattern

Master the Backtracking Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Backtracking pattern.

Framework: Backtracking • Interview Prep: Tested at FAANG • Explore all Backtracking problems & invariants →

How to Recognize This Pattern

Generate all permutations
No duplicate numbers

Complexity Analysis

Time Complexity

O(n × n!)

Space Complexity

O(n)

Frequently Asked Questions

What is the optimal time and space complexity for Permutations?

The optimal solution for Permutations achieves O(n × n!) runtime complexity and requires O(n) auxiliary space. There are n! permutations, each costing O(n) to build and copy — O(n × n!) time. The recursion depth is n and the path holds n elements — O(n) space.

How do I identify that Permutations requires the Backtracking pattern?

In technical interviews, look for key problem signals: Generate all permutations; No duplicate numbers. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Backtracking strategy.

What critical edge cases must be handled in Permutations?

Essential edge cases to verify include: Empty array — return [[]]; Single element — one permutation; Repeated values — not in this problem; Permutations II adds a sort-and-skip guard. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Permutations?

Permutations is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at LinkedIn, Microsoft, Amazon.

Permutations LeetCode Solution