Recursion & backtracking

You’ll recognise it when

• The question says every, all or list: all subsets, all orderings, every way to split, place or fill something.
• The input is tiny: n up to about 20 for subsets, or about 10 for orderings. Those limits are a hint that exponential time is expected.
• You build an answer piece by piece, and you can tell early that a partial answer is hopeless: it already went over a budget, or two queens already attack each other.
• Equal values in the input must not produce the same answer twice.

If the question only wants how many ways, or the best one, and the same smaller question keeps coming up, dynamic programming is usually much faster.

The idea

Think of trying on outfits. You pick a shirt, then trousers to go with it, then shoes. When you’ve seen that combination, you take the shoes off and try the next pair. When you’ve tried every pair, you take the trousers off too and try the next trousers. You never undress completely to start over: you undo only the last choice.

Every “list them all” problem is a tree of choices. The root is “nothing chosen yet”, each edge adds one choice, and each leaf is a finished candidate. Backtracking walks that tree depth-first while keeping a single shared path of the choices made so far. Each step down has three parts:

path.append(choice)   # choose
backtrack(...)        # explore everything that starts with this path
path.pop()            # un-choose: path is exactly as it was before

The un-choose step is what lets one list serve the whole tree. The second trick is pruning: if a partial path can never become an answer, return at once and skip its whole subtree.

How it works

The running example: from nums = [2, 1, 3, 2], find every group of values that adds up to target = 5, using each value at most once. The two 2s are interchangeable, so [2, 3] must appear only once.

Scroll through the steps and the graphic follows along. Each circle is one call and shows its remain, the amount still needed; each edge is the value chosen. You can also press play, or edit the input: try 1, 1, 1, 2 with target 3.

Why it’s correct: each call is entered with path holding exactly the choices on the way down, and it returns with path unchanged. So every branch starts from a clean slate. Building groups in index order produces each set of positions once, and skipping a repeated value at the same level removes the only other way to build the same group of values.

def groups_with_sum(nums, target):
    """Every distinct group of values from nums, each value used at most
    once, that adds up to target. Values are positive."""
    nums = sorted(nums)
    result, path = [], []

    def backtrack(start, remain):
        if remain == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                              # same value, same subtree
            if nums[i] > remain:
                break                                 # sorted: the rest are bigger too
            path.append(nums[i])
            backtrack(i + 1, remain - nums[i])
            path.pop()

    backtrack(0, target)
    return result

#include <algorithm>
#include <vector>
using namespace std;

void backtrack(const vector<int>& nums, int start, int remain,
               vector<int>& path, vector<vector<int>>& result) {
    if (remain == 0) {
        result.push_back(path);
        return;                                       // (push_back copies path)
    }
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i - 1]) {
            continue;                                 // same value, same subtree
        }
        if (nums[i] > remain) {
            break;                                    // sorted: the rest are bigger too
        }
        path.push_back(nums[i]);
        backtrack(nums, i + 1, remain - nums[i], path, result);
        path.pop_back();
    }
}

vector<vector<int>> groupsWithSum(vector<int> nums, int target) {
    sort(nums.begin(), nums.end());
    vector<int> path;
    vector<vector<int>> result;
    backtrack(nums, 0, target, path, result);
    return result;
}

import java.util.*;

class GroupsWithSum {
    private int[] nums;
    private final List<Integer> path = new ArrayList<>();
    private final List<List<Integer>> result = new ArrayList<>();

    List<List<Integer>> find(int[] values, int target) {
        nums = values.clone();
        Arrays.sort(nums);
        backtrack(0, target);
        return result;
    }

    private void backtrack(int start, int remain) {
        if (remain == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;                             // same value, same subtree
            }
            if (nums[i] > remain) {
                break;                                // sorted: the rest are bigger too
            }
            path.add(nums[i]);
            backtrack(i + 1, remain - nums[i]);
            path.remove(path.size() - 1);
        }
    }
}

Why it’s O(2ⁿ · n)

Without pruning, the tree has one node for every subset of the n values, because each call adds one new value past the last. That’s 2ⁿ calls, and copying an answer costs up to n, so the total is O(2ⁿ · n). Pruning and skipping repeats often cut the tree to a small fraction of that, but they don’t change the worst case: with small values and a large target, few branches get cut.

Orderings grow faster. The first position has n choices, the next n − 1, and so on, so there are n! leaves and the work is O(n! · n).

Extra space is O(n): the path and the recursion stack are never deeper than n. The output itself can be exponentially large.

Common mistakes

path.append(nums[i]); backtrack(i + 1, remain - nums[i])              # ✗ nums[i] is still in path
path.append(nums[i]); backtrack(i + 1, remain - nums[i]); path.pop()  # ✓ path is back as it was

result.append(path)       # ✗ every entry is the same list, empty at the end
result.append(path[:])    # ✓ a snapshot of path right now

if i > 0 and nums[i] == nums[i - 1]: continue       # ✗ also bans the second 2 deeper down
if i > start and nums[i] == nums[i - 1]: continue   # ✓ only a repeat at the same level

backtrack(start + 1, remain - nums[i])   # ✗ builds [1, 3] and [3, 1]
backtrack(i + 1, remain - nums[i])       # ✓ each group in index order, once

Variations

• Unlimited reuse. If each value may be used any number of times, recurse with i instead of i + 1. The loop still never goes back to smaller indices, so each group still appears once.
• All subsets, or subsets of size k. Record path at every call, not only at the leaves. For size k, record when len(path) == k, and prune when fewer than k - len(path) values are left.
• Orderings. Every position may take any unused value, so loop over all indices and keep a used array: mark it when you choose, clear it when you un-choose. With repeated values, sort and skip nums[i] when it equals nums[i - 1] and nums[i - 1] is not in use.
• Boards and grids. The path is the cells or squares taken so far. Mark a cell on the way down and unmark it on the way up; keep sets of used columns and diagonals for queens, or of used letters for a word search.
• Stop at the first answer. For puzzles like Sudoku or splitting into equal groups, return True as soon as one branch succeeds and let it bubble up, instead of listing everything.