Backtracking interview questions

Implement a function that returns every unique combination of reusable candidates that sums to a target.

Generate every well-formed combination of n pairs of parentheses by backtracking — add an open bracket while any remain, and a close bracket only while it stays balanced.

Split a string every possible way so that each piece is a palindrome — backtrack over cut positions, extending a piece only while it reads the same both ways.

Generate every permutation and every subset of an array with the same backtracking template — choose, recurse, and undo.

List every letter string a phone number could spell, mapping each digit to its keypad letters and backtracking through the choices.

Place N queens on an N×N board so none attack another — a classic backtracking search that places one queen per row and prunes column and diagonal conflicts.

Fill a 9×9 Sudoku grid by backtracking — try each digit in the next empty cell, checking its row, column, and 3×3 box, and undo on a dead end.