Pattern - Backtracking for Permutations

Backtracking for permutations follows this template:

$1.$ If current solution is complete, save it

$2.$ Loop through all candidates for the next position

$3.$ If candidate is valid (not used, not duplicate), add it

$4.$ Recurse

$5.$ Backtrack (remove candidate, mark as unused)

This pattern works for permutations, combinations, subsets, and more.