Skip to content

Recursion and backtracking state [ref]

Problem

  • Compute 4! recursively with a base case at 0.
  • Build every two-character binary string by appending, recursing, and popping.
  • Store a copy of path = [1, 2], then pop from path without changing the stored copy.
  • Temporarily mark the center of ["a", "b", "c"] as "#", then restore it.

Python solution

def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)

factorial(4)  # 24

res, path = [], []
def build():
    if len(path) == 2:
        res.append("".join(path))
        return
    for bit in "01":
        path.append(bit)
        build()
        path.pop()

build()
res  # ['00', '01', '10', '11']

path = [1, 2]
saved = [path[:]]
path.pop()
saved  # [[1, 2]]

row = ["a", "b", "c"]
old = row[1]
row[1] = "#"
during = row[:]
row[1] = old
(during, row)  # (['a', '#', 'c'], ['a', 'b', 'c'])