A strong answer
Brute force generates every complete candidate and then checks it. Backtracking builds candidates one choice at a time and checks constraints as it goes, so it can abandon a partial candidate the moment it breaks a rule, skipping every candidate that would extend it.
The choices form a tree: the root is the empty solution, each level makes one more choice, and leaves are complete candidates. Backtracking walks it depth first, usually with recursion and a shared partial solution: choose an option, explore recursively, then unchoose it to restore the state before trying the next option. Recording results requires copying the partial solution, because it keeps changing.
Pruning is where the speed comes from. In N-queens, placing one queen per row and keeping sets of used columns and diagonals rejects a conflicting queen immediately; for 8 queens the search tries 15,720 placements instead of considering 4.4 billion boards. Other prunes: stop a combination once its sum exceeds the target (and sort first so you can break out of the loop), only add a closing parenthesis when one is open, and skip equal values at the same level after sorting to avoid duplicate branches. Good ordering helps too: Sudoku solvers branch on the cell with the fewest legal values first.
The cost is roughly the number of nodes visited times the work per node. Without pruning that is the size of the output space, 2ⁿ for subsets or n! for permutations, which is unavoidable if every result must be listed. When the search revisits identical subproblems, for example asking the same "can the rest reach this sum?" question many times, memoizing those answers turns it into dynamic programming.
What the interviewer is listening for
- The search-tree picture and the choose/explore/unchoose pattern.
- Concrete prunes and why each one is safe.
- A realistic complexity estimate, and the link to dynamic programming.
Common mistakes
- Forgetting to undo a choice, which corrupts later branches.
- Appending the shared path instead of a copy.
- Deduplicating results at the end instead of skipping duplicate branches.