Backtracking is an algorithmic technique for finding all (or some) solutions by incrementally building candidates and abandoning ("backtracking") as soon as it determines the candidate cannot lead to a valid solution. Think of it as exploring a decision tree - make a choice, explore, then undo and try the next option.
function backtrack(path, choices):
if goal_reached(path):
result.add(copy(path))
return
for choice in choices:
if is_valid(choice):
path.add(choice) // Make choice
backtrack(path, ...) // Explore
path.remove(choice) // BacktrackBacktracking builds a decision tree where each node represents a choice. Unlike brute force, it prunes branches that cannot lead to valid solutions, making it much more efficient. The "backtrack" step undoes the last choice, allowing exploration of alternative paths.
Where k = solution length, n = choices per step. Pruning reduces this significantly.