Backtracking Template

Master backtracking techniques with these optimized code templates. Backtracking is the foundation for solving combinatorial problems like permutations, combinations, and pathfinding in grids.

For a deep dive into the theory, check out the Backtracking Concept Guide.

1. The Generic Backtracking Template

This is the “skeleton” of almost every backtracking algorithm. It follows a recursive pattern of making a choice, exploring its consequences, and then undoing that choice.

function backtrack(result, current, data) {
    // 1. Base case: Is the current solution complete?
    if (isValid(current)) {
        result.push([...current]); // Add a copy
        return;
    }

    // 2. Iterate through available candidates
    for (let candidate of getCandidates(data, current)) {
        if (isPossible(candidate, current)) {
            // 3. Make a choice (State Change)
            current.push(candidate);

            // 4. Recurse to explore this branch
            backtrack(result, current, data);

            // 5. Backtrack (Undo State Change)
            current.pop();
        }
    }
}

def backtrack(result, current, data):
    # 1. Base case: Is the current solution complete?
    if is_valid(current):
        result.append(current[:]) # Add a copy
        return

    # 2. Iterate through available candidates
    for candidate in get_candidates(data, current):
        if is_possible(candidate, current):
            # 3. Make a choice (State Change)
            current.append(candidate)

            # 4. Recurse to explore this branch
            backtrack(result, current, data)

            # 5. Backtrack (Undo State Change)
            current.pop()

public void backtrack(List<List<Integer>> result, List<Integer> current, int[] data) {
    // 1. Base case: Is the current solution complete?
    if (isValid(current)) {
        result.add(new ArrayList<>(current)); // Add a copy
        return;
    }

    // 2. Iterate through available candidates
    for (int candidate : getCandidates(data, current)) {
        if (isPossible(candidate, current)) {
            // 3. Make a choice (State Change)
            current.add(candidate);

            // 4. Recurse to explore this branch
            backtrack(result, current, data);

            // 5. Backtrack (Undo State Change)
            current.remove(current.size() - 1);
        }
    }
}

void backtrack(vector<vector<int>>& result, vector<int>& current, vector<int>& data) {
    // 1. Base case: Is the current solution complete?
    if (isValid(current)) {
        result.push_back(current); // Adds a copy in C++
        return;
    }

    // 2. Iterate through available candidates
    for (int candidate : getCandidates(data, current)) {
        if (isPossible(candidate, current)) {
            // 3. Make a choice (State Change)
            current.push_back(candidate);

            // 4. Recurse to explore this branch
            backtrack(result, current, data);

            // 5. Backtrack (Undo State Change)
            current.pop_back();
        }
    }
}

func backtrack(result *[][]int, current []int, data []int) {
    // 1. Base case: Is the current solution complete?
    if isValid(current) {
        // Must make a deep copy in Go
        temp := make([]int, len(current))
        copy(temp, current)
        *result = append(*result, temp)
        return
    }

    // 2. Iterate through available candidates
    for _, candidate := range getCandidates(data, current) {
        if isPossible(candidate, current) {
            // 3. Make a choice (State Change)
            current = append(current, candidate)

            // 4. Recurse to explore this branch
            backtrack(result, current, data)

            // 5. Backtrack (Undo State Change)
            current = current[:len(current)-1]
        }
    }
}

def backtrack(result, current, data)
  # 1. Base case: Is the current solution complete?
  if is_valid?(current)
    result << current.dup # Add a copy
    return
  end

  # 2. Iterate through available candidates
  get_candidates(data, current).each do |candidate|
    if is_possible?(candidate, current)
      # 3. Make a choice (State Change)
      current << candidate

      # 4. Recurse to explore this branch
      backtrack(result, current, data)

      # 5. Backtrack (Undo State Change)
      current.pop
    end
  end
end

Code Breakdown

The template relies on three main markers:

State: Usually represented by current (the path taken so far).
Choices: The for loop that explores all possible next steps.
Constraints: The isValid check to decide when to stop.

  graph LR
    A["State: []"] --> B[Choice: 1]
    B --> C["State: [1]"]
    C --> D[Explore Sub-trees]
    D -- "Backtrack" --> E["State: []"]
    E --> F[Choice: 2]
    F --> G["State: [2]"]

2. Common Variations

Most interview problems are specific variations of this generic template.

A. Permutations

Used when you need all possible orderings. If this is what you need, see Problem 1: Permutations.

Visual Logic:

  graph TD
    Root["[]"] --> A["[1]"]
    Root --> B["[2]"]
    A --> AB["[1,2]"]
    A --> AC["[1,3]"]
    AB -- "Backtrack" --> A
    AC -- "Backtrack" --> A

function permute(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);

    function backtrack(current) {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(nums[i]);
            backtrack(current);
            current.pop();
            used[i] = false;
        }
    }
    backtrack([]);
    return result;
}

def permute(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False

    backtrack([])
    return result

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, boolean[] used) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        current.add(nums[i]);
        backtrack(result, current, nums, used);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    vector<bool> used(nums.size(), false);
    backtrack(result, current, nums, used);
    return result;
}

void backtrack(vector<vector<int>>& result, vector<int>& current, vector<int>& nums, vector<bool>& used) {
    if (current.size() == nums.size()) {
        result.push_back(current);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true;
        current.push_back(nums[i]);
        backtrack(result, current, nums, used);
        current.pop_back();
        used[i] = false;
    }
}

func permute(nums []int) [][]int {
    var result [][]int
    used := make([]bool, len(nums))
    var backtrack func([]int)
    backtrack = func(current []int) {
        if len(current) == len(nums) {
            temp := make([]int, len(current))
            copy(temp, current)
            result = append(result, temp)
            return
        }
        for i, u := range used {
            if u { continue }
            used[i] = true
            backtrack(append(current, nums[i]))
            used[i] = false
        }
    }
    backtrack([]int{})
    return result
}

def permute(nums)
  result = []
  used = Array.new(nums.length, false)

  backtrack = ->(current) do
    if current.length == nums.length
      result << current.dup
      return
    end

    nums.each_with_index do |num, i|
      next if used[i]
      used[i] = true
      current << num
      backtrack.call(current)
      current.pop
      used[i] = false
    end
  end

  backtrack.call([])
  result
end

B. Subsets

Used when you need to generate all possible combinations of any length. See Problem 2: Subsets.

Visual Logic:

  graph TD
    Root["[]"] --> S1["[1]"]
    S1 --> S12["[1,2]"]
    S12 --> S123["[1,2,3]"]
    Root --> S2["[2]"]
    S2 --> S23["[2,3]"]
    Root --> S3["[3]"]

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(0, []);
    return result;
}

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

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

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

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    backtrack(result, current, 0, nums);
    return result;
}

void backtrack(vector<vector<int>>& result, vector<int>& current, int start, vector<int>& nums) {
    result.push_back(current);
    for (int i = start; i < nums.size(); i++) {
        current.push_back(nums[i]);
        backtrack(result, current, i + 1, nums);
        current.pop_back();
    }
}

func subsets(nums []int) [][]int {
    var result [][]int
    var backtrack func(int, []int)
    backtrack = func(start int, current []int) {
        temp := make([]int, len(current))
        copy(temp, current)
        result = append(result, temp)
        for i := start; i < len(nums); i++ {
            backtrack(i+1, append(current, nums[i]))
        }
    }
    backtrack(0, []int{})
    return result
}

def subsets(nums)
  result = []
  backtrack = ->(start, current) do
    result << current.dup
    (start...nums.length).each do |i|
      current << nums[i]
      backtrack.call(i + 1, current)
      current.pop
    end
  end
  backtrack.call(0, [])
  result
end

Practice

The best way to learn backtracking is to see it in action across different constraint types.

Master the basics: Start with Subsets and Permutations.
Add constraints: Try Combinations and Generate Parentheses.
Scale up: Challenge yourself with a Sudoku Solver.