Backtracking
Build a solution one choice at a time, undo each choice after exploring it, and cut off branches that cannot succeed.
The problem
Some questions ask for every arrangement that satisfies rules, or for the count of them:
- All subsets of a set.
- All orderings of
nitems. - Ways to place 8 queens on a chessboard so that none attack another.
You cannot write the nested loops because the number of loops depends on the input. You need code that makes one choice, moves on to the next, and can go back.
1 of 9