Backtracking
Backtracking systematically explores all possible solutions by building candidates incrementally and abandoning (backtracking from) a candidate as soon as it's determined to be invalid. It's essentially a depth-first search through the solution space. Backtracking is the go-to approach for combinatorial problems like generating permutations, combinations, subsets, and solving constraint satisfaction problems.
When to Use
- →You need to generate all permutations, combinations, or subsets
- →You need to solve constraint satisfaction problems (Sudoku, N-Queens)
- →You need to find all paths or configurations that satisfy certain conditions
- →The problem asks for 'all possible' results or 'every valid' arrangement
- →You can prune invalid branches early to avoid exponential blowup
Approach
The backtracking template has three key components: a base case (when a valid solution is found, add it to results), a loop that tries each possible choice at the current step, and a recursive call followed by undoing the choice (backtracking).
For subset/combination problems, use a start index to avoid revisiting earlier elements. For permutation problems, use a visited set or swap elements. For problems with duplicates, sort first and skip consecutive equal elements at the same decision level.
Pruning is what makes backtracking practical. Before making a choice, check if it can possibly lead to a valid solution. For example, in N-Queens, check column, diagonal, and anti-diagonal conflicts before placing each queen. Good pruning can reduce exponential time dramatically.
Code Template
// Subsets (power set)
function subsets(nums) {
const result = [];
function backtrack(start, current) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1, current);
current.pop(); // backtrack
}
}
backtrack(0, []);
return result;
}
// Permutations
function permute(nums) {
const result = [];
function backtrack(current, remaining) {
if (remaining.length === 0) {
result.push([...current]);
return;
}
for (let i = 0; i < remaining.length; i++) {
current.push(remaining[i]);
backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
current.pop();
}
}
backtrack([], nums);
return result;
}
// Combination sum with pruning
function combinationSum(candidates, target) {
const result = [];
candidates.sort((a, b) => a - b);
function backtrack(start, remaining, current) {
if (remaining === 0) { result.push([...current]); return; }
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // pruning
current.push(candidates[i]);
backtrack(i, remaining - candidates[i], current);
current.pop();
}
}
backtrack(0, target, []);
return result;
}