Technical Interviews: Everything You Need to Master Recursion & Backtracking
Every recursion and backtracking problem follows one of these patterns…
Recursion, often an underused gem in technical interviews, is a technique that can simplify many complex problems into easier ones. It’s like solving a puzzle by breaking it down into smaller pieces.
Backtracking, which uses recursion, allows us to discard paths that don’t lead to a solution, saving precious time.
This is the third article in a larger series on Technical Interview patterns. In the previous post, I introduced the Two Pointers Technique for array problems and how to use it.
Here, I’ll focus on the Recursion and Backtracking techniques — and how they can offer the most elegant and clear solutions in coding interviews.
Recursion & Backtracking
Recursion is a technique where the solution to a problem depends on solutions to smaller instances of the same problem. A recursive function calls itself with a simpler version of the original problem, gradually reducing the problem size until it reaches a base case, which is directly solvable.
Backtracking is a refined brute force approach that recursively builds paths for the solutions and abandons a path (“backtracks”) as soon as it determines that it can’t lead to a solution.
What’s its Advantage?
- Recursion simplifies code by making it shorter and easier to understand compared to iterative solutions.
- Backtracking makes search more efficient by eliminating unnecessary paths and searching only potentially successful paths.
Reminder💡: Use recursion carefully because it can sometimes lead to excessive function calls and stack usage, which can cause high time complexity and — in the worst case — stack overflow errors!
How Can You Recognise it?
- Decomposable into Smaller Instances
- Implicit Tree Structure: nodes are states or “choices”.
- Permutations and Combinations
Solved Examples in Python — Easy Level
Q1. Given the head of a linked list and an integer val, write a recursive function that removes all the nodes of the linked list that has Node.val == val, and returns the new head.
class Solution(object):
def removeElements(self, head, val):
# Add your code here
Starting with recursion can be tricky.
Try to identify the base case first. The base case for a linked list can be a node that points to None. We can then recursively return nodes (‘head.next’), skipping the ones that match the integer ‘val’, until we reach and return None.
class Solution(object):
"""
Remove all elements from a linked list of
integers that have value 'val'.
Parameters:
head (list node): The head of the linked list.
val (int): The value to remove from the list.
Returns:
list node: The head of the modified linked list.
"""
def removeElements(self, head, val):
# Base case: If the list is empty (head is None),
# return None
if head is None:
return None
# Recursive case: Call the function on the next
# node
head.next = self.removeElements(head.next, val)
# If the current node's value is the one we're
# removing, skip it
return head.next if head.val == val else headMedium Level
Q2. Given a string containing digits from 2–9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
- 0 ≤ digits.length ≤ 4
- digits[i] is a digit in range [2, 9]
class Solution(object):
def letterCombinations(self, digits):
# Add your code here
Drawing the backtracking tree is a helpful first step to visualise how to find the solution. It allows us to see all the potential paths and understand how backtracking explores each one via a depth-first search.
class Solution:
def letterCombinations(self, digits):
"""
Generate all possible letter combinations for
a string of digits.
This function uses backtracking to create all
possible combinations of letters that correspond
to the input string of digits, where each digit
maps to a set of letters as on a telephone keypad.
Parameters:
digits (str): A string containing digits from
2 to 9.
Returns:
(list of str): A list of all possible letter
combinations.
"""
if not digits:
return []
# Mapping of digits to corresponding letters,
# like on a telephone keypad
phone_map = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
# Backtracking function to build combinations
def backtrack(combination, next_digits):
# If there are no more digits to check, we have
# a complete combination
if len(next_digits) == 0:
output.append(combination)
else:
# Iterate over all letters which the current
# digit can represent
for letter in phone_map[next_digits[0]]:
# Append the current letter to the
# combination and proceed with the
# next (remaining) digits.
backtrack(combination + letter, next_digits[1:])
# List to hold the final combinations.
output = []
# Initialise backtracking with an empty combination
# and the input digits.
backtrack("", digits)
return outputHard Level
Q3. The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer ‘n’, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ indicate a queen and an empty space, respectively.
class Solution(object):
def solveNQueens(self, n):
# Add your code hereWe can solve the n-queens by using a depth-first search backtracking approach as before. The base case here is when ‘p == n’ or when all n queens have successfully been placed on all ‘p’ rows.
The decision at each backtracking tree node then becomes clear.
We check if:
- The column ‘q’ is not already occupied by another queen (‘q not in queens’).
- Placing a queen won’t result in an attack along a diagonal. This is checked by ensuring the difference between the current row and column (‘p — q’) hasn’t appeared before (‘p — q not in xy_dif’) and the sum (‘p + q’) hasn’t either (‘p + q not in xy_sum’).
That’s the key part. If after placing a queen, we find in later calls that we can’t place any more queens without a conflict, the function will backtrack and try the next column ‘q’.
def solveNQueens(self, n):
"""
Solve the n-queens puzzle and return all distinct
solutions.
Parameters:
n (int): The size of the chessboard and the number
of queens.
Returns:
list of list of str: A list of solutions, where each
solution is a list of strings representing the
chessboard.
"""
def backtrack(queens, xy_dif, xy_sum):
# p represents the current row we are trying to
# place a queen in.
p = len(queens)
# If we have placed n queens, we have found a
# solution.
if p == n:
result.append(queens)
return
# Try to place a queen in each column of the
# current row.
for q in range(n):
# Check if the current column is safe from
# attacks.
if q not in queens and p - q not in xy_dif and p + q not in xy_sum:
# Place the queen and move to the next row.
DFS(queens + [q], xy_dif + [p - q], xy_sum + [p + q])
# Initialise the result list to store all solutions.
result = []
# Start the DFS with an empty board configuration.
backtrack([], [], [])
# Build the board representation for each solution.
return [["." * i + "Q" + "." * (n - i - 1) for i in sol] for sol in result]It’s your turn now! Test your understanding with the following two questions and share your solution in the comments below. These are real coding questions presented to candidates in Google, Microsoft and Amazon interviews.
Q1. Given a string ‘s’, partition ‘s’ such that every substring of the partition is a palindrome. Return all possible palindrome partitions of ‘s’.
- Example 1. Input: s = “aab”, Output: [[“a”,”a”,”b”],[“aa”,”b”]]
- Example 2. Input: s = "a", Output: [["a"]]
class Solution(object):
def partition(self, s):
# Add your code hereQ2. There are ‘n’ children standing in a line. Each child is assigned a rating value given in the integer array ‘ratings’.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbours.
Return the minimum number of candies you need to have to distribute the candies to the children.
- Example 1. Input: ratings = [1,0,2], Output: 5
- Example 2. Input: ratings = [1,2,2], Output: 4
class Solution(object):
def candy(self, ratings):
# Add your code hereThanks for reading this, remember to clap up to 50 times 👏🏻 , highlight 🔍 and share your feedback 💬!
Sources:
