Backtracking

At each step, you "choose" a candidate option (e.g. place a queen, pick a number for a permutation), recursively "explore" further with that choice made, and once that recursive branch returns, "un-choose" (undo the choice) before trying the next option — this restores the state so the next candidate at this level starts from a clean slate, which is what lets the same recursive function explore every branch of the decision tree.

Without pruning, backtracking explores the full exponential search space (e.g. every possible arrangement), which is intractable for even moderately sized inputs. Pruning checks partial candidates against constraints as early as possible and abandons a branch the moment it's known to be invalid — e.g. in N-Queens, checking for conflicts after placing each queen rather than only after placing all of them — dramatically cutting the number of branches actually explored.

At each recursive level, choose one of the remaining (not-yet-used) elements to place next, mark it used, recurse to fill the remaining positions, then unmark it and try the next unused element. When the current permutation reaches full length, record it. This explores all n! orderings by systematically trying every choice at every position and undoing each choice before trying the next.

Plain brute force generates and checks every possible complete candidate, including ones that were already clearly invalid partway through construction. Backtracking is brute force with early termination — it checks validity incrementally as a partial solution is built and abandons a branch the instant it becomes invalid, avoiding the wasted work of completing (and then rejecting) doomed candidates. The state space explored is the same in the worst case, but pruning typically makes the practical runtime far better.