Backtracking Questions Placement
19 min read
Uncategorized
Advertisement Placement
Backtracking Questions for Placement 2026 (with Solutions)
Last Updated: March 2026
Overview
Backtracking is a systematic way of trying out different sequences of decisions until a solution is found. It's essentially a refined brute force approach that eliminates paths that won't lead to a solution. Backtracking is crucial for solving constraint satisfaction problems, permutations, combinations, and puzzles like N-Queens and Sudoku.
Companies Focused on Backtracking
- Google: N-Queens, word search, combination sum
- Amazon: Subsets, permutations, palindrome partitioning
- Microsoft: Letter combinations of phone number, generate parentheses
- Meta: Restore IP addresses, word break II
- Adobe: Combination sum, target sum
- Uber: Route finding with constraints
Core Concepts
Backtracking Template
def backtrack(candidate, path, result):
# Base case: found a valid solution
if is_valid_solution(path):
result.append(path[:]) # Add copy
return
# Try each candidate
for next_candidate in get_candidates(candidate):
# Make a choice
path.append(next_candidate)
# Explore further
backtrack(next_candidate, path, result)
# Undo the choice (backtrack)
path.pop()
Key Principles
- Choice: What choices do we have at each step?
- Constraints: What constraints must be satisfied?
- Goal: When do we have a complete solution?
Time Complexity
Backtracking is generally exponential:
- Permutations: O(n!)
- Combinations: O(2^n)
- N-Queens: O(n!)
- Sudoku: O(9^m) where m is empty cells
Pruning Strategies
# Early termination if current path can't lead to solution
if current_sum > target:
return # Prune this branch
# Skip duplicates
if i > start and nums[i] == nums[i-1]:
continue
20 Frequently Asked Coding Questions
Question 1: N-Queens
Problem: Place n queens on an n×n chessboard so that no two queens attack each other.
class Solution:
def solveNQueens(self, n):
result = []
board = [['.' for _ in range(n)] for _ in range(n)]
def is_safe(row, col):
# Check column
for i in range(row):
if board[i][col] == 'Q':
return False
# Check upper-left diagonal
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# Check upper-right diagonal
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
# Found a solution
solution = [''.join(row) for row in board]
result.append(solution)
return
for col in range(n):
if is_safe(row, col):
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.' # Backtrack
backtrack(0)
return result
# Optimized with sets
def solveNQueensOptimized(self, n):
result = []
cols = set()
diag1 = set() # row - col (constant for upper-left to lower-right)
diag2 = set() # row + col (constant for upper-right to lower-left)
def backtrack(row, state):
if row == n:
result.append([''.join(row) for row in state])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
state[row][col] = 'Q'
backtrack(row + 1, state)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
state[row][col] = '.'
board = [['.' for _ in range(n)] for _ in range(n)]
backtrack(0, board)
return result
# Driver Code
n = 4
sol = Solution()
print(len(sol.solveNQueens(n))) # Output: 2
for solution in sol.solveNQueens(n):
for row in solution:
print(row)
print()
Time Complexity: O(n!)
Space Complexity: O(n²) for board, O(n) for recursion
Question 2: Sudoku Solver
Problem: Solve a Sudoku puzzle by filling the empty cells.
class Solution:
def solveSudoku(self, board):
"""
board: 9x9 grid with '.' for empty cells
"""
def is_valid(row, col, num):
# Check row
for x in range(9):
if board[row][x] == num:
return False
# Check column
for x in range(9):
if board[x][col] == num:
return False
# Check 3x3 box
start_row = row - row % 3
start_col = col - col % 3
for i in range(3):
for j in range(3):
if board[i + start_row][j + start_col] == num:
return False
return True
def solve():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(i, j, num):
board[i][j] = num
if solve():
return True
board[i][j] = '.' # Backtrack
return False
return True
solve()
# Driver Code
board = [
["5", "3", ".", ".", "7", ".", ".", ".", "."],
["6", ".", ".", "1", "9", "5", ".", ".", "."],
[".", "9", "8", ".", ".", ".", ".", "6", "."],
["8", ".", ".", ".", "6", ".", ".", ".", "3"],
["4", ".", ".", "8", ".", "3", ".", ".", "1"],
["7", ".", ".", ".", "2", ".", ".", ".", "6"],
[".", "6", ".", ".", ".", ".", "2", "8", "."],
[".", ".", ".", "4", "1", "9", ".", ".", "5"],
[".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
sol = Solution()
sol.solveSudoku(board)
for row in board:
print(row)
Time Complexity: O(9^(n×n)) in worst case
Space Complexity: O(n²)
Question 3: Permutations
Problem: Generate all permutations of an array of distinct integers.
class Solution:
def permute(self, nums):
result = []
n = len(nums)
def backtrack(start):
if start == n:
result.append(nums[:])
return
for i in range(start, n):
# Swap
nums[start], nums[i] = nums[i], nums[start]
# Recurse
backtrack(start + 1)
# Backtrack (swap back)
nums[start], nums[i] = nums[i], nums[start]
backtrack(0)
return result
# Alternative: Using visited array
def permuteVisited(self, nums):
result = []
n = len(nums)
visited = [False] * n
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(n):
if not visited[i]:
visited[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
visited[i] = False
backtrack([])
return result
# Driver Code
nums = [1, 2, 3]
sol = Solution()
print(sol.permute(nums))
# Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
Time Complexity: O(n × n!)
Space Complexity: O(n)
Question 4: Permutations II (with duplicates)
Problem: Generate all unique permutations when array may contain duplicates.
class Solution:
def permuteUnique(self, nums):
result = []
nums.sort() # Sort to handle duplicates
n = len(nums)
visited = [False] * n
def backtrack(path):
if len(path) == n:
result.append(path[:])
return
for i in range(n):
# Skip if already used
if visited[i]:
continue
# Skip duplicates: if previous same element not used, skip current
if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:
continue
visited[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
visited[i] = False
backtrack([])
return result
# Driver Code
nums = [1, 1, 2]
sol = Solution()
print(sol.permuteUnique(nums))
# Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Time Complexity: O(n × n! / k!) where k is number of duplicates
Space Complexity: O(n)
Question 5: Subsets
Problem: Generate all possible subsets (power set) of an array.
class Solution:
def subsets(self, nums):
result = []
n = len(nums)
def backtrack(start, path):
result.append(path[:])
for i in range(start, n):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# Alternative: Cascading
def subsetsCascading(self, nums):
result = [[]]
for num in nums:
result += [curr + [num] for curr in result]
return result
# Driver Code
nums = [1, 2, 3]
sol = Solution()
print(sol.subsets(nums))
# Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Time Complexity: O(n × 2^n)
Space Complexity: O(n)
Question 6: Subsets II (with duplicates)
Problem: Generate all unique subsets when array may contain duplicates.
class Solution:
def subsetsWithDup(self, nums):
result = []
nums.sort() # Sort to group duplicates
n = len(nums)
def backtrack(start, path):
result.append(path[:])
for i in range(start, n):
# Skip duplicates
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# Driver Code
nums = [1, 2, 2]
sol = Solution()
print(sol.subsetsWithDup(nums))
# Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
Time Complexity: O(n × 2^n)
Space Complexity: O(n)
Question 7: Combination Sum
Problem: Find all combinations that sum to target (reuse allowed).
class Solution:
def combinationSum(self, candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # Reuse allowed
path.pop()
backtrack(0, [], target)
return result
# Driver Code
candidates = [2, 3, 6, 7]
target = 7
sol = Solution()
print(sol.combinationSum(candidates, target))
# Output: [[2, 2, 3], [7]]
Time Complexity: O(N^(T/M)) where T=target, M=min(candidate)
Space Complexity: O(T/M)
Question 8: Combination Sum II
Problem: Find all unique combinations (each number used once).
class Solution:
def combinationSum2(self, candidates, target):
result = []
candidates.sort()
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
# Skip duplicates
if i > start and candidates[i] == candidates[i-1]:
continue
# Early termination
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return result
# Driver Code
candidates = [10, 1, 2, 7, 6, 1, 5]
target = 8
sol = Solution()
print(sol.combinationSum2(candidates, target))
# Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Time Complexity: O(2^n)
Space Complexity: O(n)
Question 9: Combination Sum III
Problem: Find all combinations of k numbers that sum to n.
class Solution:
def combinationSum3(self, k, n):
result = []
def backtrack(start, path, remaining):
if len(path) == k:
if remaining == 0:
result.append(path[:])
return
for i in range(start, 10):
if i > remaining:
break
path.append(i)
backtrack(i + 1, path, remaining - i)
path.pop()
backtrack(1, [], n)
return result
# Driver Code
k = 3
n = 7
sol = Solution()
print(sol.combinationSum3(k, n)) # Output: [[1, 2, 4]]
Time Complexity: O(C(9, k))
Space Complexity: O(k)
Question 10: Generate Parentheses
Problem: Generate all combinations of well-formed parentheses.
class Solution:
def generateParenthesis(self, n):
result = []
def backtrack(path, open_count, close_count):
if len(path) == 2 * n:
result.append(''.join(path))
return
# Can add opening bracket
if open_count < n:
path.append('(')
backtrack(path, open_count + 1, close_count)
path.pop()
# Can add closing bracket
if close_count < open_count:
path.append(')')
backtrack(path, open_count, close_count + 1)
path.pop()
backtrack([], 0, 0)
return result
# Driver Code
n = 3
sol = Solution()
print(sol.generateParenthesis(n))
# Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Time Complexity: O(4^n / √n) - Catalan number
Space Complexity: O(n)
Question 11: Letter Combinations of Phone Number
Problem: Generate all possible letter combinations from phone digits.
class Solution:
def letterCombinations(self, digits):
if not digits:
return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
# Driver Code
digits = "23"
sol = Solution()
print(sol.letterCombinations(digits))
# Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Time Complexity: O(3^n × 4^m) where n=digits with 3 letters, m=digits with 4 letters
Space Complexity: O(n)
Question 12: Word Search
Problem: Find if word exists in a 2D grid.
class Solution:
def exist(self, board, word):
m, n = len(board), len(board[0])
def backtrack(i, j, index):
if index == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n:
return False
if board[i][j] != word[index]:
return False
# Mark as visited
temp = board[i][j]
board[i][j] = '#'
# Explore neighbors
found = (backtrack(i + 1, j, index + 1) or
backtrack(i - 1, j, index + 1) or
backtrack(i, j + 1, index + 1) or
backtrack(i, j - 1, index + 1))
# Restore
board[i][j] = temp
return found
for i in range(m):
for j in range(n):
if backtrack(i, j, 0):
return True
return False
# Driver Code
board = [
["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"]
]
word = "ABCCED"
sol = Solution()
print(sol.exist(board, word)) # Output: True
Time Complexity: O(m × n × 4^L) where L = word length
Space Complexity: O(L)
Question 13: Palindrome Partitioning
Problem: Partition string such that every substring is a palindrome.
class Solution:
def partition(self, s):
result = []
n = len(s)
def is_palindrome(start, end):
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_palindrome(start, end):
path.append(s[start:end+1])
backtrack(end + 1, path)
path.pop()
backtrack(0, [])
return result
# Optimized with DP preprocessing
def partitionOptimized(self, s):
n = len(s)
# Precompute palindrome table
dp = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]):
dp[i][j] = True
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if dp[start][end]:
path.append(s[start:end+1])
backtrack(end + 1, path)
path.pop()
backtrack(0, [])
return result
# Driver Code
s = "aab"
sol = Solution()
print(sol.partition(s)) # Output: [["a", "a", "b"], ["aa", "b"]]
Time Complexity: O(n × 2^n)
Space Complexity: O(n²) for DP table
Question 14: Restore IP Addresses
Problem: Restore all valid IP addresses from a string of digits.
class Solution:
def restoreIpAddresses(self, s):
result = []
n = len(s)
if n < 4 or n > 12:
return result
def backtrack(start, parts, path):
if parts == 4:
if start == n:
result.append('.'.join(path))
return
# Try 1 to 3 digits
for length in range(1, 4):
if start + length > n:
break
segment = s[start:start + length]
# Check validity
if length > 1 and segment[0] == '0': # No leading zeros
continue
if int(segment) > 255:
continue
path.append(segment)
backtrack(start + length, parts + 1, path)
path.pop()
backtrack(0, 0, [])
return result
# Driver Code
s = "25525511135"
sol = Solution()
print(sol.restoreIpAddresses(s))
# Output: ["255.255.11.135", "255.255.111.35"]
Time Complexity: O(3^4) = O(81) - Constant!
Space Complexity: O(1)
Question 15: Target Sum
Problem: Find number of ways to assign +/- to reach target sum.
class Solution:
def findTargetSumWays(self, nums, target):
# Memoization
from functools import lru_cache
n = len(nums)
@lru_cache(maxsize=None)
def backtrack(index, current_sum):
if index == n:
return 1 if current_sum == target else 0
# Add or subtract
add = backtrack(index + 1, current_sum + nums[index])
subtract = backtrack(index + 1, current_sum - nums[index])
return add + subtract
return backtrack(0, 0)
# Space optimized DP
def findTargetSumWaysDP(self, nums, target):
total = sum(nums)
# S1 - S2 = target
# S1 + S2 = total
# 2*S1 = target + total
# Check if possible
if abs(target) > total or (target + total) % 2 != 0:
return 0
subset_sum = (target + total) // 2
dp = [0] * (subset_sum + 1)
dp[0] = 1
for num in nums:
for j in range(subset_sum, num - 1, -1):
dp[j] += dp[j - num]
return dp[subset_sum]
# Driver Code
nums = [1, 1, 1, 1, 1]
target = 3
sol = Solution()
print(sol.findTargetSumWays(nums, target)) # Output: 5
Time Complexity: O(n × sum)
Space Complexity: O(n × sum) or O(sum)
Question 16: Beautiful Arrangement
Problem: Count arrangements where ith position is divisible by ith number or vice versa.
class Solution:
def countArrangement(self, n):
count = [0]
visited = [False] * (n + 1)
def backtrack(position):
if position > n:
count[0] += 1
return
for num in range(1, n + 1):
if not visited[num]:
if num % position == 0 or position % num == 0:
visited[num] = True
backtrack(position + 1)
visited[num] = False
backtrack(1)
return count[0]
# Driver Code
n = 3
sol = Solution()
print(sol.countArrangement(n)) # Output: 3
# Valid: [1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 2, 1]
Time Complexity: O(k) where k is number of valid permutations
Space Complexity: O(n)
Question 17: Matchsticks to Square
Problem: Determine if matchsticks can form a square.
class Solution:
def makesquare(self, matchsticks):
total = sum(matchsticks)
if total % 4 != 0:
return False
side = total // 4
matchsticks.sort(reverse=True) # Try larger first
sides = [0] * 4
def backtrack(index):
if index == len(matchsticks):
return all(s == side for s in sides)
for i in range(4):
if sides[i] + matchsticks[index] <= side:
sides[i] += matchsticks[index]
if backtrack(index + 1):
return True
sides[i] -= matchsticks[index]
# Optimization: if side is empty, skip others
if sides[i] == 0:
break
return False
return backtrack(0)
# Driver Code
matchsticks = [1, 1, 2, 2, 2]
sol = Solution()
print(sol.makesquare(matchsticks)) # Output: True
Time Complexity: O(4^n) worst case, much better with pruning
Space Complexity: O(n)
Question 18: Increasing Subsequences
Problem: Find all different increasing subsequences of length >= 2.
class Solution:
def findSubsequences(self, nums):
result = []
def backtrack(start, path):
if len(path) >= 2:
result.append(path[:])
used = set() # Avoid duplicates at this level
for i in range(start, len(nums)):
if nums[i] in used:
continue
if not path or nums[i] >= path[-1]:
used.add(nums[i])
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# Driver Code
nums = [4, 6, 7, 7]
sol = Solution()
print(sol.findSubsequences(nums))
# Output: [[4, 6], [4, 6, 7], [4, 6, 7, 7], [4, 7], [4, 7, 7], [6, 7], [6, 7, 7], [7, 7]]
Time Complexity: O(2^n)
Space Complexity: O(n)
Question 19: Gray Code
Problem: Generate n-bit gray code sequence.
class Solution:
def grayCode(self, n):
"""
Reflect and prefix method
"""
result = [0]
for i in range(n):
# Reflect and add 2^i
result += [x + (1 << i) for x in reversed(result)]
return result
# Backtracking approach
def grayCodeBacktrack(self, n):
result = []
visited = set()
def backtrack(current):
if len(result) == (1 << n):
return True
for i in range(n):
next_num = current ^ (1 << i)
if next_num not in visited:
visited.add(next_num)
result.append(next_num)
if backtrack(next_num):
return True
result.pop()
visited.remove(next_num)
return False
result.append(0)
visited.add(0)
backtrack(0)
return result
# Driver Code
n = 2
sol = Solution()
print(sol.grayCode(n)) # Output: [0, 1, 3, 2]
Time Complexity: O(2^n)
Space Complexity: O(2^n)
Question 20: Expression Add Operators
Problem: Add operators (+, -, *) to get target value.
class Solution:
def addOperators(self, num, target):
result = []
n = len(num)
def backtrack(index, path, eval_val, last_operand):
if index == n:
if eval_val == target:
result.append(path)
return
for i in range(index, n):
# Skip numbers with leading zeros
if i > index and num[index] == '0':
break
curr_str = num[index:i+1]
curr_num = int(curr_str)
if index == 0:
# First number
backtrack(i + 1, curr_str, curr_num, curr_num)
else:
# Addition
backtrack(i + 1, path + '+' + curr_str,
eval_val + curr_num, curr_num)
# Subtraction
backtrack(i + 1, path + '-' + curr_str,
eval_val - curr_num, -curr_num)
# Multiplication
backtrack(i + 1, path + '*' + curr_str,
eval_val - last_operand + last_operand * curr_num,
last_operand * curr_num)
backtrack(0, "", 0, 0)
return result
# Driver Code
num = "123"
target = 6
sol = Solution()
print(sol.addOperators(num, target))
# Output: ["1+2+3", "1*2*3"]
Time Complexity: O(4^n) - 3 choices at each position, n-1 positions
Space Complexity: O(n)
MCQ Questions
Question 1
What is the time complexity of generating all permutations of n elements?
- A) O(2^n)
- B) O(n!)
- C) O(n²)
- D) O(n log n)
Question 2
What is the key principle of backtracking?
- A) Divide and conquer
- B) Make choice, explore, undo choice
- C) Dynamic programming
- D) Greedy selection
Question 3
How many solutions exist for N-Queens when n=4?
- A) 0
- B) 1
- C) 2
- D) 4
Question 4
Which pruning technique is commonly used in backtracking?
- A) Early termination when solution is impossible
- B) Sorting
- C) Hashing
- D) Memoization
Question 5
What is the space complexity of recursive backtracking?
- A) O(1)
- B) O(n) for recursion stack
- C) O(2^n)
- D) O(n!)
Interview Tips for Backtracking
-
Master the template:
- Choice: What options do we have?
- Constraints: What limits our choices?
- Goal: When is the solution complete?
-
Optimization techniques:
- Sort input for early termination
- Use pruning to eliminate invalid branches
- Memoization for repeated subproblems
- Bit manipulation for state representation
-
Common patterns:
- Subsets/Combinations: Include/exclude pattern
- Permutations: Swap or visited array
- Constraint satisfaction: Validity checking
-
Debugging tips:
- Draw the recursion tree
- Trace through small examples
- Check base cases carefully
- Verify backtracking (undo operation)
-
When to use backtracking:
- Finding all/combinations of solutions
- Constraint satisfaction problems
- When exhaustive search is acceptable
- Problems with clear state transitions
Frequently Asked Questions
Q1: When should I use backtracking vs dynamic programming?
A: Use backtracking when you need all solutions or when problem has constraints to satisfy. Use DP when problem has overlapping subproblems and optimal substructure, and you need optimal solution.
Q2: How can I optimize backtracking solutions?
A: Use pruning (early termination), memoization, sort input for better pruning, and use appropriate data structures (bit masks, sets) for state representation.
Q3: What is the difference between subsets and permutations?
A: Subsets consider elements without regard to order (combinations). Permutations consider all possible orderings of elements.
Q4: How do I handle duplicates in backtracking?
A: Sort the input first. Skip elements that are same as previous and at the same recursion level (not at different levels).
Q5: What are some real-world applications of backtracking?
A: Sudoku solvers, crossword puzzles, scheduling problems, graph coloring, constraint satisfaction problems in AI, regex matching.
Master these backtracking problems to excel in technical interviews. Focus on recognizing the patterns and practicing the template until it becomes second nature.
Advertisement Placement
Explore this topic cluster
More resources in Uncategorized
Use the category hub to browse similar questions, exam patterns, salary guides, and preparation resources related to this topic.