Backtracking Permutation Generation

Description

A permutation uses every element exactly once, in some order. Unlike with subsets, which elements are included is fixed; only the order varies. At each position, any element not yet placed could come next, including ones earlier in the input. There are n! permutations (5,040 for n = 7), so the job is to list them without missing or repeating any. This skill covers the used[] backtracking, duplicates, and the iterative generators real code uses.

We'll go from simple to more technical:

1. The pattern: a used[] array, so any unplaced element can go next.
2. A second flavor: duplicates, with sorting and equal copies taken in order.
3. Where permutation search shows up (small schedules, brute-force checks).
4. What breaks it: the subsets loop, missing releases, and unsorted dedup.

The approach

Fill the positions one at a time. For each position, try every element that isn't placed yet, and recurse to fill the rest. A used[] array remembers which elements are already in the current arrangement. After the recursive call returns, take the element back out and mark it free again, so the next branch can use it. That undo step is the "backtracking".

For [1, 2, 3], the choices form a tree. Each level picks one unused element:

void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));          // every element placed
        return;
    }
    for (int i = 0; i < nums.length; i++) {             // every position considers ALL elements...
        if (used[i]) continue;                          // ...except the ones already placed
        used[i] = true;
        current.add(nums[i]);
        backtrack(nums, used, current, result);
        current.remove(current.size() - 1);
        used[i] = false;                                // available again for other orderings
    }
}

def backtrack(nums: list[int], used: list[bool], current: list[int], result: list[list[int]]) -> None:
    if len(current) == len(nums):
        result.append(current[:])                      # every element placed
        return
    for i in range(len(nums)):                         # every position considers ALL elements...
        if used[i]:
            continue                                   # ...except the ones already placed
        used[i] = True
        current.append(nums[i])
        backtrack(nums, used, current, result)
        current.pop()
        used[i] = False                                # available again for other orderings

The loop always starts at 0. That's the difference from subsets, whose loop only looks forward and so can only keep elements in their original order. With sorted input, trying elements in index order produces the permutations in dictionary order, as in the tree above.

A second flavor: duplicates in the input

With repeated values, swapping two equal elements gives the same permutation twice. [1, 1, 2] has 6 orderings of its positions but only 3 distinct permutations: 1 1 2, 1 2 1 and 2 1 1. The fix: sort the input so equal values sit together, then only let equal copies be placed in their original left-to-right order.

Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;   // take equal copies in order
    ...
}

nums.sort()
for i in range(len(nums)):
    if used[i]:
        continue
    if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
        continue                                       # take equal copies in order
    ...

!used[i - 1] means the earlier equal copy isn't placed yet. Using this copy first would only repeat an ordering the earlier copy already produces. The sort matters: in [1, 2, 1] the two 1s aren't neighbors, the check never fires, and every permutation appears twice.

Where you'll see it

Testing every order of a few concurrent operations, to shake out race conditions, lists permutations. So does trying every order of five steps in a small pipeline. Factorial growth limits it to a handful of elements. Past about a dozen, real systems switch to heuristics or dynamic programming.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why can't permutations use the start-index loop from subsets?

2. What does nums[i] == nums[i - 1] && !used[i - 1] skip, and why does it need sorted input?

3. What goes wrong if used[i] = false is left out?

Key takeaways

• At every position, try every unused element: loop from 0 and track used[].
• Mark used[i] before recursing and clear it after. Record a copy of the working list, not the list itself.
• On sorted input, index order gives the permutations in dictionary order.
• For duplicates, sort, then skip a value whose earlier equal copy is unused.
• With n! results, O(n * n!) is unavoidable. Keep n small, or produce permutations one at a time.