1. Concept library
  2. Data Structures & Algorithms
  3. Module 6: Recursion and backtracking

Concept

Backtracking templates

Backtracking builds a solution one choice at a time and undoes the last choice when it leads nowhere. One template covers subsets, permutations, combinations and constraint puzzles.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain the choose, explore, undo pattern
  2. Write a backtracking solution for subsets or permutations
  3. Spot the bug of appending the working list instead of a copy

In practice

A few lines that show Backtracking templates doing its job.

Python
def subsets(nums):
    result, current = [], []

    def explore(start):
        result.append(current.copy())
        for i in range(start, len(nums)):
            current.append(nums[i])      # choose
            explore(i + 1)               # explore
            current.pop()                # unchoose
    explore(0)
    return result

subsets([1, 2, 3])   # 8 subsets

The common mistake

Watch for

Appending current itself to the results instead of a copy. Every entry then refers to the same list, which is empty by the time the function returns.

What to know first

Your roadmap puts these before Backtracking templates, unless you already know them.

How it stays learned

Once a session shows you understand Backtracking templates, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Base cases and the call stack
Next in the moduleMemoisation →