Permutations

Approach Summary

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

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

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;
}

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;
}

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

How to Recognize This Pattern

Generate all permutations
No duplicate numbers

Complexity Analysis

Time Complexity

O(n × n!)

Space Complexity

O(n)