Day 5 of 30 days of Data Structures and Algorithms and System Design Simplified — Backtracking Technique
Welcome back peeps. Hope all’s well. In this post we will cover Backtracking technique as follows —
What and Why Backtracking(in 2–3 sentences)?
How does Backtracking work?
Important Patterns and Techniques in Backtracking Questions
Most Important Questions with Solutions
Tips and Techniques to solve Backtracking Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Backtracking Technique
Importance : High
Note : New backtracking questions with solutions will be added everyday. So keep checking this post everyday.
Let’s dive in!
What is Backtracking?
Backtracking is a technique which is used to solve a series of sub problems each of which may have many solutions to the sub problem.
It uses recursive calls to find the solution by building the solution step by step. The sub problems that doesn’t give rise to the solution of the problem based on the constraints given to solve the problem are eliminated.
Backtracking is all about following a systematic way to go through all the possible configurations of the search space for the given problem.
Examples of backtracking problems —
N- Queen problem
Tower of Hanoi problem
Hamiltonian Cycle problem
How does Backtracking work?
Backtracking is a problem-solving technique that involves exploring all possible solutions to a problem by incrementally building a solution and then undoing (or “backtracking” on) a choice when it is determined that it cannot be part of a valid solution. This technique is often used to solve problems that involve finding all possible solutions or finding the one with certain properties.
Backtracking works by incrementally building a solution, and at each step, it checks if the current solution is valid. If it is not, it undoes the previous step and tries a different approach. This process continues until all possible solutions have been explored or a solution that meets certain criteria is found.
Backtracking uses the brute force approach to find the desired output.
In backtracking the algorithm tries to find a sequence path to the solution which has intermediate checkpoints from where the problem can backtrack if no feasible/desired solution is found for the give problem.
There are three points — start point, intermediate check points and end points.
The algorithm terminates when there are no more solutions to the first sub-problems.
Important Patterns and Techniques in Backtracking Questions
Backtracking is applied to —
- Decision problems to find the feasible solution
- Enumeration problem to find the set of all the feasible solution
- Optimization problem to find the best solution
It’s applied in the cases where —
Let’s say you have to make a series decisions where —
Each decision leads to a new set of choices
More than one sequences can be the solution of the problem
So, you can apply backtracking in order to try out various sequences of decision until you find the solution that works for the given problem.
Patterns —> Questions like below belong to backtracking ( not limited to):
N-Queen problems
Word Search problems
Find Permutations/ Combinations of string or numbers
Calculate subsets of string/numbers
Important patterns and techniques in backtracking questions include understanding the problem constraints, identifying the decisions that can be undone, and recognizing the appropriate time to use backtracking.
Most Important Questions with Solutions
Note : New backtracking questions with solutions will be added every day. So keep checking this post everyday.
Golden rule is — Learn by doing/implementing.
In this part, we will see some of the most important backtracking questions.
Generate Parentheses
Question —
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example :
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]Solution :
Main Logic/Idea —
The gist is — Take a stack, add open parentheses if the count of openP is less than n, if closeP ( which means count of closed parentheses) is less than openP then only add closed Parentheses to the stack. Once the count of Open parentheses, closed parentheses and n becomes equal then join it into a list.
Implementation —
def generateParenthesis(self, n: int) -> List[str]:
stck, ans= [],[]
def bt(openP,closeP):
if openP < n:
stck.append("(")
bt(openP+1,closeP)
stck.pop()
if closeP < openP:
stck.append(")")
bt(openP, closeP+1)
stck.pop()
if openP==closeP==n:
ans.append("".join(stck))
bt(0,0)
return ansQuestion Link
Similar Pattern —
Check if a Parentheses String Can Be Valid
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Combination Sum
Question —
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.Solution :
Main Logic/Idea —
The main logic here is the all along you have two choices. Either to add the candidate element and calculate the total by adding the added candidate to check if its equal to the target element OR not add the candidate element and skip to the next element ( backtrack ) and reiterate the whole process until the total is equal to the target or greater than target.
Implementation —
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
def cSum(i,curr,total):
if target == total:
ans.append(curr.copy())
return
if total > target or i >=len(candidates):
return
curr.append(candidates[i])
cSum(i,curr,total+candidates[i])
curr.pop()
cSum(i+1,curr,total)
cSum(0,[],0)
return ansQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Subsets
Question —
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]Solution :
Main Logic/Idea —
The main logic here is similar to the previous question. Either add the element and calculate the subsets or don’t add the element ( backtrack) and reiterate the process until index becomes greater than length of nums.
Implementation —
def subsets(self, nums: List[int]) -> List[List[int]]:
ans, sub = [],[]
def calSets(i):
if i >= len(nums):
ans.append(sub.copy())
return
sub.append(nums[i])
calSets(i+1)
sub.pop()
calSets(i+1)
calSets(0)
return ansQuestion Link
Similar Pattern —
Count Number of Maximum Bitwise-OR Subsets
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Word Search
Question —
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: trueSolution :
Main Logic/Idea —
The gist is — For every row and column, add the character element to the visit set and then recursively do depth first search to all the directions ( left, right, up and down). If the word is found then return True else backtrack and find the word at the other positions. Lastly if the word is not found then return False.
Note : This is one the best problem to understand backtracking
Implementation —
def exist(self, board: List[List[str]], word: str) -> bool:
row, col = len(board), len(board[0])
visitPath = set()
def wordSearch(r,c,i):
if i ==len(word):
return True
if ( (r<0 or c<0 or r >=row or c >=col or word[i]!= board[r][c] or
(r,c) in visitPath)):
return False
visitPath.add((r,c))
ans = ( wordSearch(r+1,c, i+1) or
wordSearch(r,c-1, i+1) or
wordSearch(r-1,c, i+1) or
wordSearch(r,c+1, i+1))
visitPath.remove((r,c))
return ans
for r in range(row):
for c in range(col):
if wordSearch(r,c,0): return True
return FalseQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Complexity Analysis
The time complexity of recursive calls ( i.e recursion) is O(2^N) if the function calls itself twice or O(3^N) if it calls itself thrice and so on. So, the complexity of backtracking can be generalized to O(T^N) where T is the no of times the function recursively calls itself. ( Though sometimes some optimizations could be done).
Tips and Techniques to solve Backtracking Questions Fast.
Backtracking questions can solved with 3 techniques—
Start by making a decision tree.
- Add the candidate element and see if it matches the required target/output
- Don’t add the candidate and skip to the next candidate element
- Check if the target equals the total. If yes, then return the solution( feasible solutions can be many) and if no then backtrack and re-iterate the process.
Remember, backtracking solution can be one feasible solution, set of all feasible solution or the best solution.
Two points to remember —
Backtracking is implemented using recursion( best to use recursive DFS) to generate all the possible solutions to the given problem.
The base case in the backtracking solution is the where the recursive call can terminate and return the result.
Hope this helps!
That’s it for now. Day 6 : Greedy Technique coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
