Permutations & Used-State Tracking

Foundations

In the first lesson, each element faced one decision, in or out, in a fixed order. Now, what if order matters, so the question at each step is which element comes next, and any element not used yet is a candidate?

Build the arrangement one position at a time. Keep a used flag for every index: at each step, try each index whose flag is off, set the flag, append the element, recurse, then pop it and clear the flag on return. Clearing on return is what lets a later branch use that element again. A full-length path is one permutation, and n elements give n! of them.

Arrange nums = [7, 1, 5, 3, 6]. Place 7 and mark it used; then 1, marked too. The third position may take any unused element, 5, 3, or 6, and each choice recurses. When the branch under 5 returns, 5 is unmarked, and 3 takes the third position instead. Five positions with 5, 4, 3, 2, and 1 choices give 5! = 120 permutations.

Case Scenario

Permutations asks for every ordering of the distinct integers in nums. Each position takes any element not used yet, so a used flag per index marks what the current path holds, and clearing it on return frees the element for the next branch. For nums = [1, 2, 3], the six orderings come out as [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

The direct approach fills every position with any element, nⁿ sequences in all, then throws away those that repeat an element. For 3 elements that is 27 sequences to keep 6; for 8 it is over 16 million to keep 40,320. A repeat is visible the moment an element is placed twice, long before the sequence is complete.