LeetCode Patterns Flashcards: Backtracking, Decision Trees, Pruning, Permutations

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.

At each position in the input, make a binary decision: include the current element or exclude it. Start with an empty subset and recurse through the elements. When you include an element, add it to the current subset and recurse to the next position. After that recursive call returns, remove the element to backtrack and recurse without it. When you reach past the last element, the current subset is one valid result. This generates all two to the power of n subsets. The decision tree has n levels with two branches each.

At each position in the permutation, try every remaining unused element. Track which elements have been used with a boolean array or by swapping elements in place. Choose an unused element for the current position, mark it as used, recurse to fill the next position, then unmark it to backtrack. When all positions are filled, record the permutation. The decision tree has n choices at the first level, n minus one at the second, and so on, producing n factorial total permutations.

Start with the first candidate number and a remaining target. At each step, either include the current candidate, subtracting its value from the remaining target and staying at the same index since reuse is allowed, or skip it and move to the next candidate. If the remaining target reaches zero, record the current combination as valid. If it goes negative or all candidates are exhausted, backtrack. To avoid duplicate combinations in a different order, only consider candidates at the current index or later, never earlier ones.

Start from each cell matching the first character. From each cell, explore all four directions looking for the next character, marking cells as visited to avoid revisiting. If the path matches the entire word, return true. If the current cell does not match or is already visited, backtrack by unmarking the cell and returning false. The key constraint is that each cell can only be used once per path, enforced by the visited marking. After exploring all paths from a cell, unmark it so other starting points can use it.

Pruning eliminates branches of the decision tree that cannot lead to valid solutions, avoiding unnecessary recursive calls. Without pruning, backtracking degenerates into brute-force enumeration. Examples include stopping exploration when the current sum exceeds the target in combination sum, skipping duplicate elements in permutation generation, and checking row, column, and diagonal conflicts before placing a queen in the N-queens problem. Good pruning can reduce exponential time dramatically. ---