Every ordering
A permutation is an arrangement of all elements in some order. A set of n distinct elements has n factorial permutations, since you have n choices for the first slot, n minus one for the second, and so on down to one.
The placement approach
Backtracking builds a permutation slot by slot:
- Maintain a used marker for each element and a growing path.
- At each level, loop over all elements and pick any one not yet used.
- Mark it used, append it to the path, recurse, then unmark and pop to backtrack.
- When the path length equals n, you have a complete permutation.
The swap approach
An alternative fixes one position at a time by swapping the current index with each later index, recursing, then swapping back. It avoids the separate used array but mutates the input in place, so the restore swap is essential.
Handling duplicates
With repeated values, sort the input and, at each level, skip a value equal to its predecessor unless that predecessor is currently used. This keeps each distinct ordering once.
Key idea
Permutations come from choosing, at each slot, any element not yet placed, yielding n factorial orderings that backtracking walks by marking and unmarking elements.