Backtracking Algorithm Common Patterns and Code Template

This article is an advanced version of a long-ago Detailed Explanation of Backtracking Algorithm. Once you understand the framework, you'll realize that backtracking algorithm problems follow a common pattern.

This article addresses several questions:

What is the backtracking algorithm? What are the techniques for solving problems related to it? How can you learn the backtracking algorithm? Is there a pattern to writing backtracking algorithm code?

In fact, the backtracking algorithm can essentially be considered the same as what we commonly refer to as the DFS algorithm. Their subtle differences are explained in detail in Several Issues About DFS and Backtracking Algorithm. This article focuses on backtracking without delving into those differences.

Abstractly speaking, solving a backtracking problem is essentially a process of traversing a decision tree, where each leaf node of the tree contains a valid solution. By traversing the entire tree and collecting the solutions at the leaf nodes, you can obtain all valid solutions.

When standing at a node on the backtracking tree, you only need to consider three questions:

1. Path: the choices you have already made.
2. Choice List: the choices you can currently make.
3. End Condition: the condition under which you reach the bottom level of the decision tree and can no longer make choices.

If you don't understand these terms yet, that's okay. We will use the classic backtracking problem "permutations" later to help you understand what these terms mean. For now, just keep them in mind.

In terms of code, the framework for the backtracking algorithm is:

result = []
def backtrack(path, choice_list):
    if end_condition_met:
        result.add(path)
        return
    
    for choice in choice_list:
        make_choice
        backtrack(path, choice_list)
        undo_choice

The core idea is to make choices before the recursive call and undo those choices after the recursive call within the for loop. It's quite simple.

What do we mean by making and undoing choices, and what is the underlying principle of this framework? Let's unravel these mysteries by exploring the "Permutations" problem in detail!

Permutations Problem

LeetCode problem #46 "Permutations" asks you to return all possible permutations of a given array nums.

We all did permutation and combination math problems in high school and know that there are n! permutations for n distinct numbers. How did we exhaustively list all permutations back then?

For example, given the numbers [1,2,3], you wouldn't list them randomly. Typically, you would:

First, fix the first position as 1, then the second position can be 2, making the third position 3; then change the second position to 3, making the third position 2; then change the first position to 2, and exhaust the last two positions...

This is essentially backtracking, something we intuitively used in high school. Some might even draw the following backtracking tree:

By traversing this tree from the root and recording the numbers on the path, you get all permutations. We can call this tree the "decision tree" of the backtracking algorithm.

Why is it called a decision tree? Because at each node, you are making a decision. For instance, if you are at the red node in the following diagram:

You have to decide whether to take the branch with 1 or the branch with 3. Why only 1 and 3? Because the branch with 2 is behind you, a choice you already made, and permutations do not allow repeating numbers.

Now we can clarify the terms from the beginning: [2] is the "path," recording your past choices; [1,3] is the "choice list," indicating your current options; the "termination condition" is reaching the bottom leaf nodes of the tree, which here means the choice list is empty.

If you understand these terms, you can consider the "path" and "choice" list as attributes of each node in the decision tree, as shown in the diagram with several blue nodes:

Our defined backtrack function acts like a pointer, moving through this tree while correctly maintaining the attributes of each node. Whenever it reaches a bottom leaf node, the "path" is a complete permutation.

Furthermore, how do you traverse a tree? This shouldn't be hard. Recall from the previous article Framework Thinking for Learning Data Structures that various search problems are essentially tree traversal problems. The traversal framework for a multi-way tree is as follows:

void traverse(TreeNode root) {
    for (TreeNode child : root.childern) {
        // operations needed at the preorder position
        traverse(child);
        // operations needed at the postorder position
    }
}

void traverse(TreeNode* root) {
    for (TreeNode* child : root->childern) {
        // operations needed at the preorder position
        traverse(child);
        // operations needed at the postorder position
    }
}

def traverse(root: TreeNode):
    for child in root.children:
        # operations needed at the preorder position
        traverse(child)
        # operations needed at the postorder position

func traverse(root *TreeNode) {
    for _, child := range root.children {
        // operations needed at the preorder position
        traverse(child)
        // operations needed at the postorder position
    }
}

var traverse = function(root) {
    for (var i = 0; i < root.children.length; i++) {
        // operations needed at the preorder position
        traverse(root.children[i]);
        // operations needed at the postorder position
    }
}

Pre-order and post-order traversals are merely two useful time points. Let me illustrate this with a diagram:

Pre-order traversal code executes before entering a node, while post-order traversal code executes after leaving a node.

Recall our earlier discussion: "path" and "choice" are attributes of each node. The function must properly handle these attributes as it traverses the tree, which requires actions at these two special time points:

Now, do you understand the core framework of the backtracking algorithm?

for choice in choice_list:
    # make a choice
    remove choice from choice_list
    path.add(choice)
    backtrack(path, choice_list)
    # undo the choice
    path.remove(choice)
    add choice back to choice_list

By making a choice before recursion and undoing the choice after recursion, we can correctly determine the choice list and path for each node.

Next, let's directly look at the full permutation code:

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    // main function, input a set of non-repeating numbers, return all permutations
    List<List<Integer>> permute(int[] nums) {
        // record the "path"
        LinkedList<Integer> track = new LinkedList<>();
        // elements in the "path" are marked as true to avoid reuse
        boolean[] used = new boolean[nums.length];
        
        backtrack(nums, track, used);
        return res;
    }

    // path: recorded in track
    // choice list: elements not in track in nums (used[i] is false)
    // end condition: all elements in nums have appeared in track
    void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
        // trigger the end condition
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // exclude illegal choices
            if (used[i]) {

                // nums[i] is already in track, skip
                continue;
            }
            // make a choice
            track.add(nums[i]);
            used[i] = true;
            // go to the next level of decision tree
            backtrack(nums, track, used);
            // cancel the choice
            track.removeLast();
            used[i] = false;
        }
    }
}

class Solution {
private:
    vector<vector<int>> res;
public:
    // main function, input a set of non-repeating numbers, return all permutations
    vector<vector<int>> permute(vector<int>& nums) {
        // record the "path"
        vector<int> track;
        // elements in the "path" are marked as true to avoid reuse
        vector<bool> used(nums.size(), false);

        backtrack(nums, track, used);
        return res;
    }

    // path: recorded in track
    // choice list: elements not in track in nums
    // end condition: all elements in nums have appeared in track
    void backtrack(vector<int>& nums, vector<int>& track, vector<bool>& used) {
        // trigger the end condition
        if (track.size() == nums.size()) {
            res.push_back(track);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // exclude illegal choices
            if (used[i]) {

                // nums[i] is already in track, skip
                continue;
            }
            // make a choice
            track.push_back(nums[i]);
            used[i] = true;
            // enter the next level of decision tree
            backtrack(nums, track, used);
            // cancel the choice
            track.pop_back();
            used[i] = false;
        }
    }
};

from typing import List

class Solution:
    def __init__(self):
        self.res = []

    # main function, input a group of non-repeating numbers, return all permutations
    def permute(self, nums: List[int]) -> List[List[int]]:
        # record the "path"
        track = []
        # elements in the "path" are marked as true to avoid reuse
        used = [False] * len(nums)
        
        self.backtrack(nums, track, used)
        return self.res

    # path: recorded in track
    # choice list: elements not in track in nums (used[i] is false)
    # end condition: all elements in nums are present in track
    def backtrack(self, nums: List[int], track: List[int], used: List[bool]):
        # trigger end condition
        if len(track) == len(nums):
            self.res.append(track.copy())
            return
        
        for i in range(len(nums)):
            # exclude invalid choices
            if used[i]: 

                # nums[i] is already in track, skip
                continue
            # make a choice
            track.append(nums[i])
            used[i] = True
            # enter the next level of decision tree
            self.backtrack(nums, track, used)
            # cancel the choice
            track.pop()
            used[i] = False

func permute(nums []int) [][]int {
    res := [][]int{}
    track := []int{}
    used := make([]bool, len(nums))
    
    backtrack(nums, track, used, &res)
    return res
}

// path: recorded in track
// choice list: elements in nums that are not in track
// termination condition: all elements in nums have appeared in track
func backtrack(nums []int, track []int, used []bool, res *[][]int) {
    // trigger the termination condition
    if len(track) == len(nums) {
        // since track is a global variable, a new
        // array needs to be created to store a
        temp := make([]int, len(track))
        copy(temp, track)
        *res = append(*res, temp)
        return
    }
    
    for i := range nums {
        // exclude illegal choices
        if used[i] {

            // pruning to avoid reusing the same number
            continue
        }
        // make a choice
        track = append(track, nums[i])
        used[i] = true
        // go to the next level of the decision tree
        backtrack(nums, track, used, res)
        // cancel the choice
        track = track[:len(track)-1]
        used[i] = false
    }
}

var permute = function(nums) {
    let res = [];
    let track = [];
    let used = new Array(nums.length).fill(false);

    // path: recorded in track
    // choice list: elements in nums that are not in track
    // end condition: all elements in nums have appeared in track
    const backtrack = (nums, track, used) => {
        // trigger the end condition
        if (track.length === nums.length) {
            res.push(track.slice());
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            // exclude illegal choices
            if (used[i]) {

                // pruning to avoid using the same number repeatedly
                continue;
            }
            // make a choice
            track.push(nums[i]);
            used[i] = true;
            // go to the next level of the decision tree
            backtrack(nums, track, used);
            // cancel the choice
            track.pop();
            used[i] = false;
        }
    }

    backtrack(nums, track, used);
    return res;
};

Here, we made some adjustments by not explicitly recording the "choice list." Instead, we use an used array to exclude elements already in track, thereby deriving the current choice list:

With this, we have explained the underlying principles of the backtracking algorithm through the permutation problem. Of course, this algorithm is not the most efficient for solving permutations. You might encounter solutions that do not use the used array and achieve the goal by swapping elements. However, those solutions are slightly harder to understand, which I will introduce in Ball and Box Model: Two Perspectives of Backtracking.

It is important to note that no matter how you optimize, the solutions all adhere to the backtracking framework, and the time complexity cannot be lower than O(N!) because exhaustive traversal of the entire decision tree is unavoidable. In the end, you must enumerate N! permutation results.

This is also a characteristic of the backtracking algorithm. Unlike dynamic programming, which can optimize overlapping subproblems, the backtracking algorithm is purely brute-force enumeration, generally with high complexity.

Final Summary

The backtracking algorithm is essentially a traversal problem of a multi-branch tree. The key is to perform some operations at the positions of pre-order and post-order traversal. The algorithm framework is as follows:

def backtrack(...):
    for choice in choice_list:
        make_choice
        backtrack(...)
        undo_choice

When writing the backtrack function, you need to maintain the "path" that has been taken and the current "choice list." When the "end condition" is triggered, record the "path" in the result set.

If you think about it, isn't the backtracking algorithm somewhat similar to dynamic programming? In our articles on dynamic programming, we repeatedly emphasized that the three key points are "state," "choice," and "base case," which correspond to the "path" taken, the current "choice list," and the "end condition"?

Both dynamic programming and backtracking algorithms abstract problems into tree structures at their core, but their approaches are entirely different. In Binary Tree Methodology (Guiding Principles), you will see a deeper comparison and connection between dynamic programming and backtracking algorithms.