A batch scheduler had to try every ordering of distinct jobs so a planner could pick a sequence that passed a later constraint. The intern nested three loops because the first ticket was always three tasks. Staging with [1, 2, 3] returned six lists. Then ops added a fourth job and there was no fourth loop in the file.

Permutations asks for every ordering of a distinct array. An array of n values is the sequence. Nested loops use that and still freeze n at compile time.

This is an interview writeup, not a backtracking lecture. The backtracking post owns choose, recurse, and undo. Here we only care about which index is being filled: swap a later value into that slot (or mark it used), then undo so the sibling sees the array as it was.

The problem

Given an int[] nums of distinct integers, return all permutations. Order of the lists does not matter. Each permutation is a rearrangement of every value exactly once.

nums = [1, 2, 3]  →  [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
nums = [0, 1]     →  [0, 1], [1, 0]
nums = [1]        →  [1]

Note: Next Permutation wants the next rearrangement in lexicographic order, in place, not the full list. Subsets wants every subset, not every ordering. Do not recycle either walk.

Nested loops freeze n

Three distinct indexes i, j, k and a uniqueness check. Correct for n = 3. A fourth value needs a fourth loop. n! does not fit in three fors.

List<List<Integer>> permuteNested(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (j == i) {
                continue;
            }
            for (int k = 0; k < n; k++) {
                if (k == i || k == j) {
                    continue;
                }
                out.add(Arrays.asList(nums[i], nums[j], nums[k]));
            }
        }
    }
    return out;
}

At three jobs this is a rounding error. At a variable n you paid a nest that does not exist: which unused value still belongs in slot i?

Swap into slot i, recurse, swap back

Index i is the slot you are filling. For each j from i to the end: swap j into i, recurse i + 1, swap back. When i == n, copy the whole array — that leaf is one permutation. The undo is the second swap. A boolean[] used plus a path is the same tree: skip a used index, mark, recurse, unmark.

Walk [1, 2, 3]. First slot takes 1, then 2, then 3.

nums = [1, 2, 3]   fill slot i

i=0  swap 0,0  [1,2,3]
  i=1  swap 1,1  [1,2,3]
    i=2  record [1,2,3]
  i=1  swap 1,2  [1,3,2]
    i=2  record [1,3,2]
  swap 1,2 back  [1,2,3]
swap 0,0 back
i=0  swap 0,1  [2,1,3]
  ... record [2,1,3], [2,3,1]; swap 0,1 back
i=0  swap 0,2  [3,2,1]
  ... record [3,2,1], [3,1,2]; swap 0,2 back

The Java is that walk. Copy at the leaf: nums is mutated on the way back down.

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    fill(0, nums, out);
    return out;
}

void fill(int i, int[] nums, List<List<Integer>> out) {
    if (i == nums.length) {
        List<Integer> row = new ArrayList<>(nums.length);
        for (int v : nums) {
            row.add(v);
        }
        out.add(row);
        return;
    }
    for (int j = i; j < nums.length; j++) {
        swap(nums, i, j);
        fill(i + 1, nums, out);
        swap(nums, i, j);
    }
}

void swap(int[] a, int x, int y) {
    int t = a[x];
    a[x] = a[y];
    a[y] = t;
}

Time is Θ(n · n!) — n! leaves, each copied in O(n). Extra space is O(n) for the call stack (and used[] if you go that way), besides the output.

Note: The second swap is the undo. Drop it and slot i stays swapped for every sibling. out.add(nums) is worse than aliasing a list: there is only one array, so every recorded row becomes the last permutation.

What interviewers usually poke next

  • used[] plus a path. Same n! tree. Skip used[j], append, recurse, pop, unmark. Preferred when the next prompt needs to skip duplicates without rewriting swaps.
  • Duplicates in nums. Permutations II: sort, and at one depth skip a value you already placed from an equal neighbor. The swap version needs the same skip, or you emit [1, 1, 2] twice.
  • Count only. Increment at the leaf; do not copy. Still n! visits unless they asked for n! as a formula and no list.
  • In-place next permutation. A different prompt: one rearrangement, lexicographically next, constant extra space. Do not generate n! rows to pick the successor.

You are done with this problem when you can say, out loud, why three nested loops die at n = 4, why the swap back is what keeps siblings honest, and why you copy nums at the leaf instead of storing the live array.