Backtracking
Build a candidate one choice at a time, and undo the last choice the moment it cannot lead anywhere.
The Call Stack: Summing a list recursively
Backtracking is depth-first search over partial answers. Make a choice, recurse, and when the recursion returns, undo the choice before trying the next one. The undo is what separates it from plain enumeration: one board, one array and one visited set are reused at every node of the tree, so the memory is the depth of the search rather than the number of candidates in it.
The search space is whatever it is: 2^n subsets, n! permutations, nine choices per empty Sudoku cell. Backtracking does not shrink those numbers. What it does is refuse to extend a candidate that is already impossible, a queen that is attacked or a running sum that has overshot the target, and every rejection at depth d deletes the entire subtree below it. That pruning is the difference between a board solved in milliseconds and one that never finishes.
So the design question is how early a constraint can be tested. The test runs at every node and has to earn its cost in branches removed. N-Queens checks one column and two diagonals in constant time per placement and kills whole subtrees with it. A check that only works on a finished candidate prunes nothing at all and leaves you with brute force.
After this you can
- Write the choose, explore, undo loop and say exactly what the undo restores
- Enumerate subsets, permutations and combinations without producing a duplicate
- Place a constraint check at the point in the tree where it cuts the most branches
- Bound a search by the shape of its tree: branching factor raised to the depth
In this order
Where people go wrong
Forgetting the undo
Whatever was changed on the way down has to be restored on the way up: pop the element, clear the visited cell, unset the column. A missing undo does not crash, it silently blocks branches that were never really used and you get too few answers.
Duplicates from unordered choices
Picking any remaining element at each level produces every combination k! times over. Only ever picking an index larger than the last is what makes each one appear once, and sorting first is what lets you skip equal siblings at the same level.
Checking after the candidate is complete
Building a full assignment and then validating it is brute force with extra bookkeeping. The check has to run on the partial candidate, before the recursive call, or no subtree is ever cut.