Backtracking: Code Templates for Permutations and Subsets

Coding Patterns - Guide to 30 Core Algorithm Patterns

Backtracking: Complete Guide with Pruning Techniques

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview.

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

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

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 that decides 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 versions of this generic template.

A. Permutations

Used when you need all possible orderings. The key addition is a used array that tracks which elements have already been placed, since permutations use every element exactly once. 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 every possible combination regardless of order. The start index prevents duplicate sets by only looking forward. 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
}

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .