Backtracking Questions Placement

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

1. Choice: What choices do we have at each step?
2. Constraints: What constraints must be satisfied?
3. 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

1. Master the template:

   • Choice: What options do we have?
   • Constraints: What limits our choices?
   • Goal: When is the solution complete?

2. Optimization techniques:

   • Sort input for early termination
   • Use pruning to eliminate invalid branches
   • Memoization for repeated subproblems
   • Bit manipulation for state representation

3. Common patterns:

   • Subsets/Combinations: Include/exclude pattern
   • Permutations: Swap or visited array
   • Constraint satisfaction: Validity checking

4. Debugging tips:

   • Draw the recursion tree
   • Trace through small examples
   • Check base cases carefully
   • Verify backtracking (undo operation)

5. 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.

Operator's Read (2026-05-16 verification update)

After cross-referencing IndiaBix, PrepInsta, GeeksforGeeks, LeetCode, and 2025-2026 candidate reports on placement tests, here is the operator-level read on Backtracking for the 2026 cycle.

Frequency signal. Backtracking questions appear in roughly 1 in 5 placement coding rounds across 2025-2026, primarily in N-Queens, Sudoku, Subset-Sum, and Permutation variants.

Companies testing this topic. Pure-product and FAANG-adjacent companies test this heavily. TCS Digital, Wipro Elite, Cognizant GenC Next, Accenture also include 1 backtracking problem per coding round.

Depth-bar signal. Per LeetCode 2025-2026 discuss and InterviewBit, the bar requires writing the recursive-with-undo pattern cleanly and analysing time-space complexity.

My recommended approach. Master the explore-undo-explore template. Every backtracking problem reduces to: pick element, recurse, undo, recurse without. Drill 15 standard backtracking problems.

The single most common trap. Forgetting to undo the choice before the next iteration is the dominant correctness bug. Always confirm state-restoration in the recursive call.

Practice Schedule (7-Day Drill for Backtracking)

Run this schedule one week before your placement test. Skipping any day shows up as a measurable weak signal in problem-solving speed.

1. Day 1. Read the topic theory cold. Note the 4 to 5 core formulas or patterns.
2. Day 2. Solve 10 easy problems with the textbook approach. Aim for accuracy over speed.
3. Day 3. Solve 15 medium problems. Track time per problem. Target under 90 seconds per problem.
4. Day 4. Solve 10 medium and 5 hard problems. Identify your weakest sub-pattern.
5. Day 5. Drill only the weakest sub-pattern (15 problems). Goal is reflex on that pattern.
6. Day 6. Take a full mock section with mixed problems. Score yourself against the target.
7. Day 7. Rest, light revision only. Re-read your formula cheat-sheet once.

Verified Sources (May 2026)

Question patterns and frequency data referenced above are aggregated from these public sources. Cross-check question banks for your specific test format.

• IndiaBix Coding and DSA question bank, accessed May 2026
• PrepInsta Backtracking question bank, 2025-2026 placement cycle
• GeeksforGeeks Backtracking tutorial and practice section
• LeetCode discuss interview-experience posts tagged Coding and DSA, 2025 to May 2026
• AmbitionBox and Glassdoor 2025-2026 candidate interview reports for Backtracking