LeetCode 46 · Medium · Backtracking

Permutations

Given an array nums of distinct integers, return every ordering of all its elements. There are n! of them, in any order.

O(n · n!)time
O(n)space besides the output
pick[] flagseach value once per path

1–4 distinct integers from −10 to 10 · 4 values already grow a 65-node tree with 24 leaves

nums and pick blue = pick[i] is true · #p = its position in perm · i = the value just chosen

perm the ordering built on the current path

decision tree one child per value not yet picked · depth d fixes position d

res 0 permutations

public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); boolean[] pick = new boolean[nums.length]; backtrack(nums, new ArrayList<>(), pick, res); return res;}private void backtrack(int[] nums, List<Integer> perm, boolean[] pick, List<List<Integer>> res) { if (perm.size() == nums.length) { res.add(new ArrayList<>(perm)); return; } for (int i = 0; i < nums.length; i++) { if (!pick[i]) { perm.add(nums[i]); pick[i] = true; backtrack(nums, perm, pick, res); perm.remove(perm.size() - 1); pick[i] = false; } }}
i
—
perm
[]
pick
—
res.size()
0

Why it works

  1. Brute force builds all nⁿ sequences (n nested choices with repeats allowed) and keeps those without a repeated value. Only n! of the nⁿ survive, so most of the work is wasted.
  2. Never offer a value twice on one path. pick[i] marks the values already in perm; the loop offers only the rest. Depth d has n − d children, so the leaves are exactly the n! orderings, each once.
  3. n! leaves, O(n) each. Copying a full perm costs n, and every inner node does an O(n) scan of pick: O(n · n!) in total. The stack, perm and pick use O(n).
  4. Pitfall: forgetting to undo. perm.remove(perm.size() - 1) and pick[i] = false must both run after the call returns, or later siblings see a value as taken and the tree loses branches. Remove by index here: on a List<Integer>, perm.remove(nums[i]) compiles but removes by index, not by value.
  5. Follow-up, Permutations II (47): with repeated values, sort and skip nums[i] when it equals nums[i − 1] and that earlier copy is not picked, the same sibling-dedupe idea as Subsets II.