The Backtracking Problem Template [Technique Tuesdays]
A step by step guide on how to approach Backtracking Problems
Hey, it’s your favorite cult leader here 🦹♂️🦹♂️
On Tuesdays, I will cover problem-solving techniques that show up in software engineering, computer science, and Leetcode Style Questions📚📚📝📝.
I put a lot of effort into creating work that is informative, useful, and independent from undue influence. If you’d like to support my writing, please consider becoming a paid subscriber to this newsletter. Doing so helps me put more effort into writing/research, reach more people, and supports my crippling chocolate milk addiction.
PS- We follow a “pay what you can” model, which allows you to support within your means, and support my mission of providing high-quality education to everyone for less than the price of a cup of coffee. Check out this post for more details and to find a plan that works for you.
Backtracking problems are notoriously difficult for many programmers to solve- both in IRL software engineering and Leetcode problems, along with graphs, recursion, and dynamic programming. We have done in-depth dives into the other types mentioned (you can search out all the previous articles over here) so now would be a good time to finish out our freaky foursome of Leetcode.
This article aims to give you a plug-and-play template with which you can approach any problem. As with any other template covered by our chocolate milk cult- the purpose is to provide you with a reliable strategy that you can use to get your thoughts going and not be overwhelmed by all the possibilities of what you can do. Since many of you are busy bees, here is tl;dr of the topics we will cover in this article-
The Big Mistake People Make When Studying Backtracking: Many people jump into backtracking (BT) without mastering recursion, a big mistake for two main reasons:
Foundation of BT: Recursion forms the basis of backtracking. Mastering recursive thinking makes the transition to BT smoother and more intuitive.
Broader Skillset: Mastering recursion enhances problem-solving skills across various domains and opens the mind to new thinking styles.
Recommendation: Focus most of your efforts on mastering recursion. Once you’ve mastered that, you can get your backtracking specific gainzz by focusing on coding solutions quickly and optimization tricks.
Steps for Tackling Recursive Problems: This template can be applied to solve recursion-based problems. We will build on it for our backtracking template, so spend a lot of time familiarizing yourself with it.
Check Termination Cases: Implement base cases first to manage the recursive leap of faith.
Do the Processing: For backtracking, mark the current state as visited for pruning and optimization.
Move to Recursive Cases: Call the recursive function on all variants.
Reset Side Effects: Undo changes to avoid unexpected bugs, especially in backtracking.
Theoretical Foundations for Backtracking: The following ideas help when talking about/implementing backtracking
State Space Tree: Visualize each state of the solution as a node in a tree.
Pruning: Eliminate possibilities that won’t lead to a solution.
Partial Candidate: Differentiate between partially and fully completed solutions for clearer thinking.
When to Use Backtracking:
Multiple Solutions: Problems with more than one solution.
Constraint Satisfaction: Solutions must meet certain constraints.
Optimization: Finding the best solution among many.
Common Problems for Backtracking:
Combinatorial problems (e.g., combinations, permutations)
Puzzle solving (e.g., Sudoku)
Path finding in graphs or mazes
Subset sum problems
Constraint satisfaction problems (e.g., map coloring)
Step-by-Step Template for Backtracking Problems:
Define the Problem: Understand requirements and constraints. This adds clarity and helps your problem-solving flow more smoothly.
Define the State Space Tree: Visualize the problem as a tree with nodes representing solution states.
Recursively Explore Solutions: Use recursion to explore possibilities.
Prune Unsuccessful Paths: Abandon paths that don’t meet constraints early.
Combine Solutions: Merge partial solutions into the final solution.
Efficiency Tips:
Use Memoization: Reuse results of expensive function calls.
Effective Pruning: Spend time on tree layout and problem definition.
Accept Performance Tradeoffs: Reduce scope for practical solutions and plan around acceptable failures to save time and effort.
If that sounds good, let’s get into the details.
I provide various consulting and advisory services. If you‘d like to explore how we can work together, reach out to me through any of my socials over here or reply to this email.
Step Zero: Avoiding the Mistake that kills your Backtracking
A surprisingly common mistake that many people make is attempting to get into BT without mastering recursion. This is a mistake for two reasons-
Recursion Forms the basis of Backtracking. Not understanding recursive thinking will significantly slow down your backtracking journey. If you master recursion, you don’t even really need to specifically worry about backtracking (the jump from Recursion to BT is much smaller than you’d think).
Mastering recursion adds a whole dimension of skills that carry over to other problem types and opens up your mind to a whole new style of thinking.
Imo, you’re better off focusing 90% of your efforts on Recursion- and only 10% on BT (that 10% should be focused mainly on getting good at coding the solutions quickly + some optimizations). That is also the reason we have multiple deep dives on recursion and no dedicated article on backtracking. If you’re not confident in your recursion, I recommend studying our various articles on Recursion before worrying about BT. Shoot me a message through one of my socials if you want to know what precisely to pick.
Even the template that we will cover today is based heavily on the recursive function template, which is covered here. You can approach every recursive problem through the following steps-
Check for termination cases- The first thing you check in every recursive function is the termination/base cases. These cases are easy to implement so you can get them out of the way relatively quickly. And once you have gone through these, you need to worry about the recursive cases. Taking care of the base cases first also allows you to implement the recursive leap of faith, which we covered on this Technique Tuesday.
Do the processing- This is generally associated with the outcome that we are expected to produce. For backtracking, you want to mark your current state as visited, which will help with with pruning and optimizations.
Move on to the recursive case- Notice how long we took to get here. We have eliminated a lot of the other moving parts so that we can focus on the recursion itself. You can now call the recursive function on all the variants you must deal with.
Reset side effects—Sometimes, you make changes to your code or states that you want to undo. This might involve resetting global variables. People often overlook this, leading to unexpected bugs, especially in Backtracking.
Let’s build on this and explore the backtracking-specific refinements. To do so, it’s helpful to understand some theoretical ideas about backtracking.
Step 1: Theoretical Foundations for Backtracking
1.1 Main Ideas
Aside from recursion, the key concepts in backtracking include:
State Space Tree: The process of backtracking can be visualized using a state space tree where each node represents a state of the solution.
Pruning: Pruning is the act of eliminating possibilities that we can be sure won’t lead to a solution. This is where backtracking gets its efficiency.
Partial Candidate: A partially completed solution. I like to differentiate between this and the complete solutions since it helps me think more clearly.
1.2 When to Use Backtracking
Backtracking is particularly useful for problems that have the following characteristics:
Multiple solutions: The problem may have more than one solution, and you need to find one or all of them.
Constraint satisfaction: The solution must satisfy certain constraints.
Optimization: You need to find the best solution among many possible ones.
Common problem types that are well-suited for backtracking include:
Combinatorial problems (e.g., generating all possible combinations or permutations)
Puzzle solving (e.g., Sudoku, crosswords)
Path finding in a graph or maze
Subset sum problems
Constraint satisfaction problems (e.g., map coloring)
By using backtracking, we can efficiently explore the solution space without generating and testing every possible combination explicitly. This makes it a powerful technique for solving problems that would otherwise be computationally infeasible.
With this background out of the way, now is a good time to get into the actual template for solving Backtracking Problems. To do so, we will break down the template into steps and talk about how each step would apply to two example problems.
Step 2: A Step-by-Step Template to Solving Backtracking Problems
1. Define the Problem
Concept: Clearly understand the problem requirements and constraints to frame it correctly with a backtracking paradigm. This seems obvious, but too many people skip this step and rush into the coding. Slowing down may seem counterintuitive in time-sensitive situations, but it can give you time to game-plan and really plan ahead.
At this step, my favorite thing to do is lay out the problem statement, constraints, and any other information the interviewer gives directly. Then, I start verbalizing every assumption, asking clarifying questions, and explicitly stating my early impressions. This buys time, establishes communication with the interviewer, and lets my mind start making mental connections for the problem.
Example: N-Queens Problem
Place N queens on an N×N chessboard so no two queens threaten each other.
Win Condition: No two queens can be in the same row, column, or diagonal.
Example: Subset Sum Problem
Determine if there is a subset of a given set with a sum equal to a specified value.
Win Condition: The subset’s sum should match the target value.
With the ground-work laid, we can jump into problem-solving step.
2. Define the State Space Tree
Concept: Visualize the problem using a tree where each node represents a state of the solution. Each path from the root to a leaf represents a potential solution.
Example: N-Queens Problem
Each level of the tree represents placing a queen in a new column.
Nodes at each level represent different rows where the queen can be placed.
Example: Subset Sum Problem
Each node represents including or excluding an element from the set.
The tree explores all subsets of the set.
3. Recursively Explore Solutions
Concept: Use recursion to explore each possibility. At each step, make a choice and recurse to explore further.
Example: N-Queens Problem
def solve_n_queens(n):
board = [[0] * n for _ in range(n)]
if solve_n_queens_util(board, 0, n):
print_board(board)
else:
print("No solution exists")
def solve_n_queens_util(board, col, n):
if col >= n:
return True
for i in range(n):
if is_safe(board, i, col, n):
board[i][col] = 1
if solve_n_queens_util(board, col + 1, n):
return True
board[i][col] = 0
return FalseExample: Subset Sum Problem
def is_subset_sum(arr, n, sum):
if sum == 0:
return True
if n == 0 and sum != 0:
return False
if arr[n - 1] > sum:
return is_subset_sum(arr, n - 1, sum)
return is_subset_sum(arr, n - 1, sum) or is_subset_sum(arr, n - 1, sum - arr[n - 1])4. Prune Unsuccessful Paths
Concept: Abandon paths that do not meet problem constraints early to avoid unnecessary computation.
Example: N-Queens Problem
def is_safe(board, row, col, n):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, n, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return TrueExample: Subset Sum Problem
If including the current element exceeds the target sum, skip it (prune that path).
5. Combine Solutions
Concept: Combine partial solutions to form the final solution. In backtracking, this typically means the base case returns a valid solution up the recursive call stack.
I’ll let you code this part for practice.
Tips for Efficient Backtracking
Use Memoization: Store results of expensive function calls and reuse them.
Effective Pruning: Implement good pruning strategies to cut down the state space. Spending some time on the tree layout and problem definition can help here.
Accept Performance Tradeoffs: In IRL Software Solutions, you can go a long way by reducing the scope of your solutions and not trying to get perfect results. By accepting failure in certain cases and planning around them- you can save a lot of engineering time and effort that can be applied to other use cases.
Backtracking is a powerful tool for solving problems with a large search space by systematically exploring all possible configurations and eliminating those that do not satisfy the constraints. With practice, understanding how to efficiently prune the search space becomes more intuitive.
To those of you that like videos, this video by the excellent Back to Back SWE is a good exploration of the topic.
If you liked this article and wish to share it, please refer to the following guidelines.
That is it for this piece. I appreciate your time. As always, if you’re interested in working with me or checking out my other work, my links will be at the end of this email/post. And if you found value in this write-up, I would appreciate you sharing it with more people. It is word-of-mouth referrals like yours that help me grow.
Looking to understand complicated ideas in AI, Software Engineering, and the money driving the developments in the Tech Industry? Join 100K+ tech professionals and sign up below to get such high-quality information delivered directly to your inbox and never miss an update. You can find all my work here or in the links below.
I regularly share mini-updates on what I read on the Microblogging sites X(https://twitter.com/Machine01776819), Threads(https://www.threads.net/@iseethings404), and TikTok(https://www.tiktok.com/@devansh_ai_made_simple)- so follow me there if you’re interested in keeping up with my learnings.
Reach out to me
Use the links below to check out my other content, learn more about tutoring, reach out to me about projects, or just to say hi.
Small Snippets about Tech, AI and Machine Learning over here
AI Newsletter- https://artificialintelligencemadesimple.substack.com/
My grandma’s favorite Tech Newsletter- https://codinginterviewsmadesimple.substack.com/
Check out my other articles on Medium. : https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Reach out to me on LinkedIn. Let’s connect: https://rb.gy/m5ok2y
My Instagram: https://rb.gy/gmvuy9
My Twitter: https://twitter.com/Machine01776819