Whether you are new to coding interviews or are already familiar with the concept of backtracking algorithms, this is the crash course for you.

In it, we will learn about an all-purpose coding template for solving backtracking problems and apply it to two LeetCode hard problems. Ready to crunch your next coding interview? Let's go!

If you just want to dive right in, you can find the course here (and linked at the bottom of this article). If you want a little more info, read on. :)

Who is the Course for and What is the Backtracking Algorithm?

This course is suitable for anyone who is preparing for coding interviews, especially those who are looking to hone their skills in solving backtracking problems.

Backtracking is a common category for questions in coding interviews. The algorithm for solving those problems usually involves recursion and building incrementally on previous states to arrive at the ultimate valid solution.

Backtracking is a favorite topic among top tech companies like Google, Microsoft, and Facebook, precisely because it requires robust reasoning and coding competence to nail those questions.

However, because of its recursive nature and complex problem definition, backtracking problems are usually a major source of confusion among devs who are preparing for coding interviews.

To address this confusion, this crash course aims to arm with you a concise, 20-line template that you can apply to the majority of backtracking problems.

Course Outline

This course runs for a total of 40 minutes and the structure is as follows:

The All-Purpose Template

For your convenience, I've copied the template over. This is exactly the same template that I use for my coding interviews, or when I'm developing algorithms for my indie games. I even used it once in my research on a non-convex optimization problem.

def is_valid_state(state):
    # check if it is a valid solution
    return True

def get_candidates(state):
    return []

def search(state, solutions):
    if is_valid_state(state):
        solutions.append(state.copy())
        # return

    for candidate in get_candidates(state):
        state.add(candidate)
        search(state, solutions)
        state.remove(candidate)

def solve():
    solutions = []
    state = set()
    search(state, solutions)
    return solutions

The first three are all helper functions, and the last and most important one, solve, is essentially the one that a LeetCode problem is asking you to write.

Solving LeetCode Problems Hands-On

We will next apply this template to solving two LeetCode hard problems: LeetCode Question 51. N-Queens and LeetCode Question 37. Sudoku Solver.

To illustrate the flexibility of the template, see below for how we solve the N-Queens problem by doing nothing fancy other than adapting the four functions (renaming solve to solveNQueens). The complete code for either problem is available in my GitHub gist.

Watch the video course to follow along my analysis and adaptation of the template.

class Solution:
    # solveNQueens is essentially the solve function
    def solveNQueens(self, n: int) -> List[List[str]]:
        solutions = []
        state = []
        self.search(state, solutions, n)
        return solutions
        
    def is_valid_state(self, state, n):
        # check if it is a valid solution
        return len(state) == n

    def get_candidates(self, state, n):
        if not state:
            return range(n)
        
        # find the next position in the state to populate
        position = len(state)
        candidates = set(range(n))
        # prune down candidates that place the queen into attacks
        for row, col in enumerate(state):
            # discard the column index if it's occupied by a queen
            candidates.discard(col)
            dist = position - row
            # discard diagonals
            candidates.discard(col + dist)
            candidates.discard(col - dist)
        return candidates

    def search(self, state, solutions, n):
        if self.is_valid_state(state, n):
            state_string = self.state_to_string(state, n)
            solutions.append(state_string)
            return

        for candidate in self.get_candidates(state, n):
            # recurse
            state.append(candidate)
            self.search(state, solutions, n)
            state.pop()

Check out the video course here:

You can access the template as well as the solutions to the two LeetCode problems (N-Queens and Sudoku Solver) in my GitHub gist:

[Algo] Backtracking Template & N-Queens Solution
[Algo] Backtracking Template & N-Queens Solution. GitHub Gist: instantly share code, notes, and snippets.

Final Thoughts

Remember that practice makes perfect, so do try applying this template to more backtracking problems on LeetCode. Best of luck crunching your next coding interview!

For more content like this, check out my YouTube channel:

Lynn’s DevLab
Hi! I’m Lynn, a newbie software engineer and hobbyist game developer. Here at my channel, you can expect to enjoy monthly technical tutorials, my project demos, and my speed paints.