Skip to main content
LeetCode Prep
CHAPTER 12 Beginner

Recursion and Backtracking

Updated: May 18, 2026
5 min read

# CHAPTER 12

Recursion and Backtracking

1. Chapter Introduction

Recursion is the act of a function calling itself. While we used basic recursion to traverse Trees, it becomes a significantly more complex weapon when applied to Backtracking. Backtracking is a methodical way of trying out all possible solutions to a problem, and "backing up" (reversing your choice) the moment you realize a path is invalid. It is the core algorithm used for generating Permutations, Combinations, Subsets, and solving puzzles like Sudoku.

2. The Three Laws of Recursion

Before jumping into Backtracking, ensure you understand the three laws every recursive function must obey:
  1. 1. The Base Case: A condition that stops the recursion. (Without it, you get a StackOverflowError).
  1. 2. State Change: The function must modify its state and move *towards* the base case (e.g., n - 1).
  1. 3. The Recursive Call: The function must call itself.

3. What is Backtracking?

Imagine navigating a physical maze.
  1. 1. You walk down Path A.
  1. 2. You hit a dead end (Base Case / Invalid State).
  1. 3. You walk *backwards* to the last intersection (Backtrack).
  1. 4. You try Path B.
In code, backtracking involves making a "choice", exploring that choice via recursion, and then "undoing" that choice after the recursion returns, so you can try the next option.

4. The Universal Backtracking Template

Memorize this template. 90% of Backtracking questions can be solved by modifying these 6 lines.
python
1234567891011121314151617 
def backtrack_template(res, path, choices):
    # 1. Base Case: Is the path a complete valid solution?
    if is_complete(path):
        res.append(path.copy()) # Must append a COPY of the path!
        return
        
    # 2. Iterate through all possible choices at this step
    for choice in choices:
        if is_valid(choice):
            # 3. MAKE A CHOICE
            path.append(choice)
            
            # 4. EXPLORE recursively
            backtrack_template(res, path, remaining_choices)
            
            # 5. UNDO THE CHOICE (Backtrack)
            path.pop()

5. Pattern 1: Generating Subsets

*Prompt:* Given an array of unique integers nums, return all possible subsets. (LeetCode 78). *Example:* [1,2] -> [[], [1], [2], [1,2]]
python
12345678910111213141516 
def subsets(nums):
    res = []
    
    def backtrack(start_index, current_path):
        # Every path is a valid subset, append it immediately
        res.append(current_path.copy())
        
        # Try adding remaining elements to the subset
        for i in range(start_index, len(nums)):
            current_path.append(nums[i])      # Make choice
            backtrack(i + 1, current_path)    # Explore (move index forward)
            current_path.pop()                # Undo choice (Backtrack)
            
    backtrack(0, [])
    return res
# Time: O(N * 2^N)

6. Pattern 2: Generating Permutations

*Prompt:* Given an array nums of distinct integers, return all the possible permutations. (Order matters: [1,2] and [2,1] are different). *The Trick:* Unlike Subsets, we don't use a start_index to move forward. We can pick *any* number for the next slot, as long as we haven't already used it in the current path.
python
123456789101112131415161718 
def permute(nums):
    res = []
    
    def backtrack(current_path):
        # Base Case: Path length equals nums length
        if len(current_path) == len(nums):
            res.append(current_path.copy())
            return
            
        for num in nums:
            if num not in current_path: # Skip used numbers
                current_path.append(num)  # Make choice
                backtrack(current_path)   # Explore
                current_path.pop()        # Undo choice
                
    backtrack([])
    return res
# Time: O(N * N!) Factorial Time

7. Pattern 3: Combinations / Combination Sum

*Prompt:* Find all unique combinations in candidates where the numbers sum to target. *Logic:*
  • Base case 1: sum == target (Append to result).
  • Base case 2: sum > target (Return/abort path).
  • To prevent duplicate combinations (like [2,2,3] and [3,2,2]), use the startindex trick from the Subsets pattern so you only explore numbers to the right.

8. Real-World Scenario: N-Queens

*Prompt:* Place N queens on an NxN chessboard such that no two queens attack each other. *Logic:*
  1. 1. Try placing a Queen in row 0, col 0.
  1. 2. Move to row 1. Try placing a Queen in col 0 (Invalid, attacked). Try col 1 (Invalid). Try col 2 (Valid!). Place Queen.
  1. 3. Move to row 2... If no column works, backtrack to row 1, remove the Queen, and move it to col 3.
This brute-force algorithmic guessing is precisely what backtracking was built for.

9. Common Mistakes

  • Appending References, not Copies: In Python or Java, if you do res.append(path), you are appending a *reference* to the list. When you path.pop() later to backtrack, it empties the list inside res too! You MUST append a copy: res.append(path[:]) or res.add(new ArrayList<>(path)).
  • Forgetting to Return: If you hit your base case, you must return to stop that branch of recursion. If you don't, it will run forever.

10. Best Practices

  • Time Complexity Expectations: Interviewers know backtracking is slow. Generating subsets is O(2^N). Generating permutations is O(N!). Do not panic trying to optimize these to O(N); they are inherently exponential problems.

11. Exercises

  1. 1. Trace the subsets algorithm on paper for the array [1, 2]. Watch how the path variable grows and shrinks.
  1. 2. In the permute algorithm, why do we need if num not in currentpath:?

12. MCQs

Question 1

What is the defining characteristic of a "Backtracking" algorithm?

Question 2

What are the three essential components every recursive Backtracking function must contain?

Question 3

When generating all possible "Subsets" of an array of size N, what is the expected Time Complexity?

Question 4

When generating all possible "Permutations" of an array of size N, what is the expected Time Complexity?

Question 5

What is a catastrophic bug that occurs when appending the valid currentpath to the result array in Python or Java?

Question 6

When generating Permutations (where order matters: [1,2] and [2,1] are valid), how does the for loop differ from generating Subsets?

Question 7

In the N-Queens problem, what triggers the Backtracking mechanism (the undo choice)?

Question 8

What happens if you forget the "Base Case" in a recursive function?

Question 9

Is Backtracking considered an optimal solution for finding the shortest path in a graph?

Question 10

How should you approach optimizing a Backtracking algorithm if it is timing out?

14. Interview Questions

  • Q: "Given a string containing digits from 2-9, return all possible letter combinations that the number could represent. (Like an old T9 mobile phone keypad)." (LeetCode 17).

15. FAQs

  • Q: Do I need to memorize all the backtracking templates?
A: Memorize the single Universal Template (Base Case, Loop, Choice, Recurse, Undo Choice). You can derive Subsets, Combinations, and Permutations by slightly tweaking the for loop parameters of that one template.

16. Summary

Backtracking is the ultimate brute-force algorithmic technique. It systematically navigates massive decision trees by making choices, exploring recursively, and "undoing" choices when a dead end is reached. Master the universal template (append, recurse, pop). Remember to always append a *copy* of your path to the result array, and explicitly state that your Time Complexity will likely be O(2^N) or O(N!).

17. Next Chapter Recommendation

Backtracking explores every single path, which is terribly slow if we re-calculate the exact same sub-problems repeatedly. How can we speed this up? In Chapter 13: Dynamic Programming Basics, we will introduce "Memoization" to cache our recursive results, turning O(2^N) nightmares into O(N) elegance.

Finish this Chapter

Save your progress on your learning path and prepare for coding interview challenges.

Previous Chapter Binary Search Trees and Heaps
Next Chapter Dynamic Programming Basics

Discussion

Join the discussion

Log in or create a free account to participate.

Sort: ·

Explore More

📖 Related Tutorials 4

🗺️ Related Roadmaps 1