Basic Backtracking Template

Medium Recursion & Backtracking Basic Recursion Original on LeetCode

Basic Backtracking Template is a medium recursion & backtracking problem solved with the basic recursion pattern. The best approach, the template, runs in O(branches^depth) time and O(depth) space.

Problem

Learn the general shape of a backtracking solution before solving specific problems. Backtracking builds a solution one choice at a time, walks down a path of choices, and undoes the last choice to try the next one when it returns.

Examples

Example 1

Input: choices = [1, 2, 3], build every sequence of length 2 without reuse
Output: [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]

Example 2

Input: N-Queens with n = 4 (the linked problem)
Output: 2 boards

Constraints

Backtracking explores a tree of choices. Its cost is roughly (number of nodes) × (work per node).

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
The template	`O(branches^depth)`	`O(depth)`

1The template

TimeO(branches^depth)Worst case visits every node of the choice tree; pruning cuts it down.

SpaceO(depth)Recursion depth plus the current path.

At each level of the recursion: if the current path is a complete answer, record a copy of it. Otherwise loop over the choices available at this level, skip invalid ones, make the choice (mutate state), recurse, then undo the choice. Every backtracking problem in this module (subsets, combinations, permutations, N-Queens, word search) fills in these four blanks: what the state is, when it is complete, which choices exist, and how to prune.

if (isComplete(state)) { record(copy(state)); return; }
for (choice : choices(state)) { if (!valid(choice)) continue;
apply(choice); backtrack(state); undo(choice); }

Java

class Solution {
    // Example: all sequences of length k from nums without reusing an element.
    public List<List<Integer>> sequences(int[] nums, int k) {
        List<List<Integer>> out = new ArrayList<>();
        backtrack(nums, k, new boolean[nums.length], new ArrayList<>(), out);
        return out;
    }

    private void backtrack(int[] nums, int k, boolean[] used, List<Integer> path, List<List<Integer>> out) {
        if (path.size() == k) {               // complete?
            out.add(new ArrayList<>(path));   // record a copy
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;            // prune invalid choice
            used[i] = true;                   // choose
            path.add(nums[i]);
            backtrack(nums, k, used, path, out);  // explore
            path.remove(path.size() - 1);     // un-choose
            used[i] = false;
        }
    }
}

Edge cases to test

Adding the shared path to the result instead of a copy
Forgetting to undo a choice

Hints

Hint 1

choose → explore → un-choose. If the state after the recursive call is not what it was before, you have a bug.

FAQ

What is the best time complexity for Basic Backtracking Template?

The template runs in O(branches^depth) time and O(depth) extra space. Worst case visits every node of the choice tree; pruning cuts it down.

Which pattern does Basic Backtracking Template use?

It is a recursion & backtracking problem that uses the basic recursion pattern. Other problems with the same pattern: Factorial of a number, Fibonacci Number, Binary Tree Inorder Traversal (Recursive).

Which edge cases should I test for Basic Backtracking Template?

Adding the shared path to the result instead of a copy; Forgetting to undo a choice.