Recursion & Backtracking

Place one queen per row in a non-conflicting column, tracking used columns and both diagonals, and backtrack when a row has no safe cell.

Fill each position with every unused element, recurse, then undo, producing all n! orderings.

Subtract a chosen number from the remaining target and recurse from the same index for reuse; record at zero, prune below zero.

Power of x to n is x times power of x to n-1, bottoming out at 1 when the exponent reaches zero; square the half-power to make it logarithmic.

For each element choose include or exclude; every complete choice sequence is one subset, giving 2^n subsets.

Recurse with the same index to allow reuse; stop at zero remaining, prune below zero, advance index to avoid reordered duplicates.

For each digit append each of its keypad letters and recurse to the next digit; record when all digits are consumed.

Total must be even, and a subset must hit total / 2; solve with a boolean DP array swept downward.

One queen per row; a column is safe if its column and both diagonals are free; backtrack when a row is stuck.

Recurse first then print for ascending order, or print first then recurse for descending order.

Recursion is a method that solves a problem by calling itself on a smaller subproblem until a base case stops it.

A sum is reachable if it was already reachable before, or reachable after subtracting the current number from it.

A boolean DP array where dp[t] is true when some subset of the numbers sums to exactly t, filled by considering each number once from high to low.

Find the largest reachable subset sum not exceeding half the total; the minimum difference is total minus twice that sum.

Loop coins outside, amounts inside, and accumulate counts to count distinct combinations with unlimited coins.

Start with the empty subset and, for each element, duplicate all existing subsets and add the element to each copy.

Fill positions one at a time, try each unused element, recurse, then undo the choice to explore all orderings.

For each digit try every mapped letter, recurse to the next digit, and record a combination when all digits are assigned.

Backtrack subtracting candidates from the remaining target, allow reuse by not advancing the index, and carry a start index to avoid duplicate combinations.

Backtrack choosing numbers in increasing order up to size K, and prune branches that cannot reach K items.

Build one Trie from all dictionary words, DFS the grid with backtracking while walking the Trie, and collect words at end-of-word nodes.

Try every starting cell, walk adjacent cells matching the word character by character, mark visited cells and unmark on backtrack.

Fill each empty cell with a digit valid in its row, column, and box; recurse; undo on dead ends until the grid is complete.