What is backtracking and how does it differ from brute force?

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning a candidate as soon as it cannot lead to a valid solution, a process called pruning. Unlike brute force which generates all possibilities and then filters, backtracking prunes invalid paths early, avoiding unnecessary work. The algorithm makes a choice, recurses to explore that choice, then undoes the choice and tries the next option. This "choose, explore, unchoose" pattern forms a decision tree.