Backtracking Problems Explained with Code

Many developers find backtracking problems intimidating because the recursive logic can feel difficult to trace at first. Backtracking problems follow a consistent pattern once you recognise it, making them far more approachable than they appear. Learning how to structure a backtracking solution correctly will give you a reliable framework for solving an entire category of interview problems with confidence.

TL;DR Summary

• Backtracking is an algorithmic technique that builds solutions incrementally and abandons a path as soon as it determines the path cannot lead to a valid solution.
• It is used to solve problems involving permutations, combinations, subsets, and constraint satisfaction.
• Backtracking problems are among the most frequently asked topics in coding interviews at top tech companies.
• Understanding how to identify, structure, and implement a backtracking solution is essential for any developer preparing for product-based company interviews in 2026.

Want to master recursion, backtracking, and advanced problem-solving patterns for top tech interviews? Explore HCL GUVI’s Data Structures and Algorithms Course, built with real coding problems, guided solutions, and interview-focused practice. 

What Is Backtracking?

Backtracking is a depth-first search based algorithmic technique that explores all possible solutions by building candidates incrementally and discarding any candidate the moment it violates the problem constraints.

Think of it like navigating a maze. You walk down a path, and if you hit a dead end, you backtrack to the last decision point and try a different direction. You keep doing this until you find the exit or exhaust all paths.

Backtracking is used when:

• You need to find all possible combinations or permutations
• You need to satisfy a set of constraints
• The solution space is too large for brute force but can be pruned
• You are solving puzzles, path problems, or assignment problems

Read More: Search Techniques in AI: The Complete Beginner Guide

How Does Backtracking Work?

Backtracking works in three steps at every recursive call.

Step 1: Choose Select a candidate from the available options at the current step.

Step 2: Explore Recurse deeper with the chosen candidate added to the current solution.

Step 3: Unchoose Remove the candidate from the current solution and try the next option. This is the backtrack step.

This choose, explore, unchoose pattern is the foundation of every backtracking solution. Once you internalise this structure, most backtracking problems become a variation of the same template.

Backtracking Problem Template

Here is the universal template for any backtracking problem in Python:

def backtrack(current_solution, remaining_choices):

    # Base case: solution is complete

    if is_complete(current_solution):

        results.append(current_solution[:])

        return

    for choice in remaining_choices:

        # Check if this choice is valid

        if is_valid(choice, current_solution):

            # Choose

            current_solution.append(choice)

            # Explore

            backtrack(current_solution, updated_choices)

            # Unchoose (backtrack)

            current_solution.pop()

Every backtracking problem maps to this template. The key differences between problems are in the base case, the validity check, and how the remaining choices are updated at each step.

Backtracking Problems with Code

Problem 1: Generate All Permutations of an Array

def permutations(nums):

    results = []

    def backtrack(current, remaining):

        if not remaining:

            results.append(current[:])

            return

        for i in range(len(remaining)):

            current.append(remaining[i])

            backtrack(current, remaining[:i] + remaining[i+1:])

            current.pop()

    backtrack([], nums)

    return results

print(permutations([1, 2, 3]))

# Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

At each step, one number is chosen from the remaining list, added to the current permutation, and the function recurses with the remaining numbers. After returning, the number is removed and the next option is tried.

Problem 2: Generate All Subsets

def subsets(nums):

    results = []

    def backtrack(start, current):

        results.append(current[:])

        for i in range(start, len(nums)):

            current.append(nums[i])

            backtrack(i + 1, current)

            current.pop()

    backtrack(0, [])

    return results

print(subsets([1, 2, 3]))

# Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Every recursive call appends the current state to results before exploring further. The start index ensures each element is only considered once and subsets are not repeated.

Problem 3: Solve the N-Queens Problem

The N-Queens problem asks you to place N queens on an N x N chessboard such that no two queens attack each other.

def solve_n_queens(n):

    results = []

    board = []

    def is_valid(row, col):

        for r, c in board:

            if c == col or abs(r - row) == abs(c - col):

                return False

        return True

    def backtrack(row):

        if row == n:

            results.append(board[:])

            return

        for col in range(n):

            if is_valid(row, col):

                board.append((row, col))

                backtrack(row + 1)

                board.pop()

    backtrack(0)

    return results

print(len(solve_n_queens(4)))  # Output: 2

For each row, the algorithm tries placing a queen in every column. The is_valid function checks that no existing queen shares the same column or diagonal. If valid, it places the queen and recurses to the next row.

Want to master recursion, backtracking, and advanced problem-solving patterns for top tech interviews? Explore HCL GUVI’s Data Structures and Algorithms Course, built with real coding problems, guided solutions, and interview-focused practice. 

Problem 4: Word Search in a Grid

def word_search(board, word):

    rows, cols = len(board), len(board[0])

    def backtrack(r, c, index):

        if index == len(word):

            return True

        if r < 0 or r >= rows or c < 0 or c >= cols:

            return False

        if board[r][c] != word[index]:

            return False

        temp = board[r][c]

        board[r][c] = "#"

        found = (backtrack(r+1, c, index+1) or

                 backtrack(r-1, c, index+1) or

                 backtrack(r, c+1, index+1) or

                 backtrack(r, c-1, index+1))

        board[r][c] = temp

        return found

    for r in range(rows):

        for c in range(cols):

            if backtrack(r, c, 0):

                return True

    return False

The cell is temporarily marked with a hash to prevent revisiting during the current path. After exploring all four directions, the cell is restored to its original value as part of the backtrack step.

Common Mistakes When Solving Backtracking Problems

1. Forgetting to Undo the Choice: Must remove the last added element before trying the next option. No undo = stale data in subsequent paths.

2. Not Restoring Modified Input: If marking visited cells or modifying state, restore the original value after recursion. Forgotten restore = corrupted state downstream.

3. Unclear Base Case: Base case must capture exactly when a valid complete solution is found. Vague base case = infinite recursion or early termination.

4. Appending Reference Instead of Copy: Always use current[:] or list(current), never just current. Appending the reference means all results point to the same list—it mutates as recursion continues, leaving garbage output.

5. Missing Pruning Condition: Validity check before each recursive call is what makes backtracking efficient. No pruning = brute force exploring dead paths.

Conclusion

As product-based companies continue to test algorithmic depth in coding interviews, backtracking remains one of the most important patterns every developer must be comfortable with. 

Mastering the choose, explore, unchoose template and applying it consistently across permutation, combination, and constraint problems will give you a reliable framework for an entire category of interview questions. Start with subsets and permutations, move to combination sum, then tackle N-Queens and word search. 

FAQ

1. What is backtracking in programming?

Backtracking is an algorithmic technique that builds solutions step by step and abandons any path that violates the problem constraints. It uses recursion to explore all possible candidates and backtracks to the previous state when a dead end is reached.

2. What is the difference between backtracking and recursion?

Recursion is a general programming technique where a function calls itself. Backtracking is a specific use of recursion where the algorithm explores choices, and if a choice leads to an invalid state, it undoes that choice and tries the next one.

3. What is the difference between backtracking and dynamic programming?

Backtracking explores all possible solutions by trying and undoing choices, making it suitable for problems requiring all valid combinations. Dynamic programming stores and reuses results of overlapping subproblems to optimise a single best solution. Backtracking is used for exhaustive search and DP is used for optimisation.

4. What are the most common backtracking problems asked in interviews?

Frequently asked backtracking problems include generating permutations and subsets, combination sum, N-Queens, Sudoku solver, word search, palindrome partitioning, and letter combinations of a phone number. These appear regularly in interviews at Google, Amazon, and Microsoft.

5. What is the time complexity of backtracking algorithms?

Time complexity varies by problem. Permutations run in O(n x n!) time. Subsets run in O(2^n) time. N-Queens runs in O(n!) time. In general, backtracking is exponential in the worst case, but pruning reduces the actual number of paths explored significantly.

6. How do I know when to use backtracking?

Use backtracking when the problem asks you to find all valid combinations, permutations, or subsets, when you need to satisfy a set of constraints, or when the problem involves placing elements on a grid or structure without conflicts.

7. Why is the unchoose step important in backtracking?

The unchoose step restores the solution to its previous state before trying the next option. Without it, the current solution carries data from previous paths, corrupting the results for all subsequent recursive calls.

8. Can backtracking be optimised?

Yes. The primary optimisation is pruning, which means adding a validity check before each recursive call to skip paths that cannot lead to a valid solution. Pruning can reduce the number of explored paths dramatically, making backtracking far more efficient than brute force in practice.