Backtracking Basics

Backtracking is disciplined trial and correction. You build a partial answer, explore one choice, undo it, then try the next choice. It is the foundation for permutations, subsets, combinations, Sudoku, N-Queens, path search, and many constraint problems.

Choose, Recurse, Undo

Backtracking is usually depth-first search over a decision tree. At each level, you choose a candidate, recurse with that choice included, then undo the choice so the next branch starts from a clean state.

Scenario: Constraint Scheduler

A team scheduler must assign engineers to shifts. Each shift needs one engineer, some engineers are unavailable, and no engineer should exceed a workload limit. A greedy assignment may get stuck. Backtracking tries an assignment, recurses, and backs out when a constraint fails.

Same Pattern in Java, Python, and JavaScript

Subsets is the cleanest starting point: for each number, choose to include it, recurse, then undo and continue.

import java.util.*;

class Subsets {
    static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

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

Cost and Pruning

Backtracking often has exponential worst-case cost. That is not automatically wrong. The right answer names the search space, the constraints, and the pruning rule. If n is too large and pruning is weak, backtracking is the wrong approach.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Generate all subsets of unique integers.
• Generate all permutations of distinct integers.
• Return combinations of candidates that sum to target; candidates can be reused.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

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

import java.util.*;
class Permute { static List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(nums, new boolean[nums.length], new ArrayList<>(), res); return res; } static void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) { if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i=0;i<nums.length;i++) if (!used[i]) { used[i]=true; path.add(nums[i]); backtrack(nums, used, path, res); path.remove(path.size()-1); used[i]=false; } } }

import java.util.*;
class CombinationSum { static List<List<Integer>> solve(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); backtrack(nums, target, 0, new ArrayList<>(), res); return res; } static void backtrack(int[] nums, int rem, int start, List<Integer> path, List<List<Integer>> res) { if (rem == 0) { res.add(new ArrayList<>(path)); return; } for (int i=start;i<nums.length && nums[i] <= rem;i++) { path.add(nums[i]); backtrack(nums, rem - nums[i], i, path, res); path.remove(path.size()-1); } } }

Solved modelWorked Interview Answer

Generate all subsets with choose, recurse, and undo. Backtracking keeps a mutable path. Copy the path when recording an answer, then undo after each recursive branch.

import java.util.*;

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

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Forgetting to undo mutable state after recursion.
• Appending the same path reference instead of a copy.
• Hiding exponential complexity.
• Failing to prune impossible branches.
• Using backtracking when constraints are too large.

Execution guardrailQuick-Start Checklist

• Define choices at each level.
• Add valid partial or complete answer at the right time.
• Choose one candidate.
• Recurse on the reduced problem.
• Undo before the next branch.
• State search-space size.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice subsets, permutations, combination sum, N-Queens, and Sudoku.
• Review recursion and call stack before complex backtracking.
• Compare brute force with constraint-guided search.