Explore all possibilities recursively and prune invalid branches early.
Backtracking is a recursive technique that builds solutions incrementally and abandons ("backtracks") partial solutions as soon as they cannot lead to a valid answer. It is used for permutations, combinations, subsets, and constraint-satisfaction problems.
Exponential in general O(2ⁿ) or O(n!) depending on problem
O(n) recursion depth
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
pick an element to add to the current path
recursively build on the choice
remove the element and try the next option
binary choice at each element (subsets, knapsack)
skip invalid choices early to reduce search space
sort input and skip duplicate elements at the same level