Lesson 6 · Core algorithms

Backtracking Algorithms

Backtracking is an algorithmic paradigm that incrementally builds candidates to the solutions and abandons a candidate ('backtracks') as soon as it determines that the candidate cannot possibly be completed to a valid solution.

The state-space tree

Backtracking problems can be visualized as a tree where each node represents a partial solution, and edges represent choices. The algorithm traverses this tree using Depth-First Search (DFS).

When a leaf node is reached, a complete solution has been formed. If the solution meets the criteria, it is recorded.

Nodes are partial states
Edges are decisions
Leaves are complete combinations or permutations

Making and undoing choices

The core pattern of backtracking involves a loop of choices at the current state. For each choice, you modify the state, recursively call the function to continue building, and then undo the modification (backtrack).

Undoing the choice is critical; it ensures that when the recursion unwinds to try the next option, the state is clean and unaffected by the abandoned path.

Choose: add to partial path
Explore: recursive call
Un-choose: remove from partial path

Key reference

Terms, operations, and practical uses

Core vocabulary

State SpaceThe set of all possible configurations or paths for a given problem.
CandidateA partial or complete solution currently being evaluated.
PruningStopping the exploration of a path as soon as it's known it cannot lead to a valid solution.

Mechanics

Recursive DepthThe depth of the recursive call stack, which usually corresponds to the number of choices made so far.
Backtrack (Undo)The crucial step of reverting a choice (e.g., popping from an array) after the recursive call returns.
Base CaseThe condition under which a candidate is complete and can be added to the final results.

Common patterns

SubsetsGenerating all possible subsets (the power set) by deciding whether to include or exclude each element.
PermutationsGenerating all possible orderings of a set, typically requiring a 'visited' array to avoid reusing elements.
CombinationsSelecting K items from N possibilities without regard to order, typically tracked via a start_index.

Code example

Generate all subsets of [1, 2]

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res
print(subsets([1, 2]))

void backtrack(int start, vector<int>& path, vector<int>& nums, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(i + 1, path, nums, res);
        path.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    backtrack(0, path, nums, res);
    return res;
}

static void backtrack(int start, List<Integer> path, int[] nums, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(i + 1, path, nums, res);
        path.remove(path.size() - 1);
    }
}
static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(0, new ArrayList<>(), nums, res);
    return res;
}

Inputnums = [1, 2]

Output[[], [1], [1, 2], [2]]

Example

Run the example step by step

Output

Pruning branches

Without pruning, backtracking is just brute-force search. Pruning involves writing conditional checks to stop exploring a path as soon as it's provably invalid.

For example, in the N-Queens problem, if placing a queen at a specific spot leads to an immediate attack, the algorithm will not explore any further placements on that board configuration, saving massive computation.

Identify invalid states early
Return immediately if state is invalid
Significantly reduces exponential time complexity

Combinations vs Permutations

Backtracking is the standard tool for generating combinatorial structures. Combinations care about selection, while permutations care about order.

To avoid duplicate subsets in combinations, pass a 'start_index' to the recursive call so elements are only picked from the remaining pool. For permutations, you must track which elements have already been used globally in the current path.

Combinations: use a start_index
Permutations: use a 'used' array or set
Sort input to easily skip duplicate values