Backtracking-Schema: Auswählen, Erkunden, Auswahl zurücknehmen

Was ist Backtracking?

# Mental model: backtracking explores a decision tree
# At each node you make a choice, go deeper, then undo it
#
# Tree for generating subsets of [1,2,3]:
#        []
#      /    \
#    [1]   []
#   / \    / \
# [1,2][1][2] []
# ...

# Every leaf is a potential solution
# Pruning cuts branches early based on constraints
print('Backtracking = DFS on decision tree with pruning')

Die Vorlage in drei Schritten

def backtrack(current_state, choices, results):
    # Base case: is current_state a complete solution?
    if is_complete(current_state):
        results.append(list(current_state))  # record solution
        return
    
    for choice in choices:
        if is_valid(choice, current_state):    # pruning condition
            # 1. CHOOSE
            current_state.append(choice)
            # 2. EXPLORE
            backtrack(current_state, choices, results)
            # 3. UNCHOOSE (backtrack)
            current_state.pop()

# Placeholder functions — filled per problem
def is_complete(state): return True
def is_valid(choice, state): return True

Einfachstes Beispiel: Alle Teilmengen

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(list(path))  # every state is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])    # CHOOSE
            backtrack(i + 1, path)  # EXPLORE
            path.pop()              # UNCHOOSE
    backtrack(0, [])
    return result

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

Die Pruning-Bedingung erkennen

def combination_sum(candidates, target):
    result = []
    candidates.sort()  # sort enables early termination
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(list(path))
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining: break   # PRUNE: sorted, so rest are bigger too
            path.append(c)            # CHOOSE
            backtrack(i, path, remaining - c)   # EXPLORE (reuse allowed)
            path.pop()                # UNCHOOSE
    backtrack(0, [], target)
    return result

print(combination_sum([2, 3, 6, 7], 7))  # [[2,2,3],[7]]

Die Wiederherstellung des Zustands ist entscheidend

# Bug: forgetting to unmark in word search
# Correct pattern for grid backtracking:
def word_search(board, word):
    m, n = len(board), len(board[0])
    def dfs(r, c, k):
        if k == len(word): return True
        if not (0<=r<m and 0<=c<n): return False
        if board[r][c] != word[k]: return False
        temp, board[r][c] = board[r][c], '#'  # CHOOSE (mark visited)
        found = any(dfs(r+dr, c+dc, k+1)
                    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)])
        board[r][c] = temp  # UNCHOOSE (restore cell)
        return found
    return any(dfs(r, c, 0) for r in range(m) for c in range(n))

board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
print(word_search([row[:] for row in board], 'ABCCED'))  # True

Den Entscheidungsbaum nachverfolgen

def combination_sum_trace(candidates, target):
    result = []
    candidates.sort()
    def backtrack(start, path, remaining, depth):
        indent = '  ' * depth
        print(f'{indent}explore({path}, remaining={remaining})')
        if remaining == 0:
            result.append(list(path))
            print(f'{indent}FOUND: {path}')
            return
        for i in range(start, len(candidates)):
            c = candidates[i]
            if c > remaining:
                print(f'{indent}PRUNE at {c}')
                break
            path.append(c)
            backtrack(i, path, remaining - c, depth + 1)
            path.pop()
    backtrack(0, [], target, 0)
    return result

combination_sum_trace([2, 3, 6, 7], 7)

Backtracking und Brute Force im Vergleich

# Compare call counts: brute force vs backtracking for permutations
import sys
calls_brute = [0]
calls_back = [0]

def brute_force_perms(nums):
    from itertools import permutations
    return list(permutations(nums))

def backtrack_perms(nums):
    result = []
    used = [False] * len(nums)
    def bt(path):
        calls_back[0] += 1
        if len(path) == len(nums):
            result.append(list(path))
            return
        for i, n in enumerate(nums):
            if not used[i]:
                used[i] = True
                path.append(n)
                bt(path)
                path.pop()
                used[i] = False
    bt([])
    return result

backtrack_perms([1,2,3,4])
print(f'Backtrack calls for 4 items: {calls_back[0]}')

Sammeln oder frühzeitig zurückkehren

# Enumerate all: collect in results list
def all_solutions(candidates):
    results = []
    def bt(path, remaining):
        if remaining == 0:
            results.append(list(path))
            return
        for c in candidates:
            if c <= remaining:
                path.append(c); bt(path, remaining - c); path.pop()
    bt([], 5)
    return results

# Find any one: return True on first success
def any_solution(candidates, target):
    def bt(path, remaining):
        if remaining == 0: return True
        for c in candidates:
            if c <= remaining:
                path.append(c)
                if bt(path, remaining - c): return True  # short-circuit
                path.pop()
        return False
    path = []
    return bt(path, target), path

Memoisation mit Backtracking

from functools import lru_cache

def word_break_all(s, wordDict):
    words = set(wordDict)
    
    @lru_cache(maxsize=None)
    def bt(start):
        if start == len(s): return ['']  # empty suffix
        result = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in words:
                for rest in bt(end):
                    result.append(word if not rest else word + ' ' + rest)
        return result
    
    return bt(0)

print(word_break_all('catsanddog', ['cat','cats','and','sand','dog']))
# ['cat sand dog', 'cats and dog']

Zeitkomplexität von Backtracking

# Complexity quick reference:
# Subsets of n elements:     O(n * 2^n)  - 2^n subsets, each copied in O(n)
# Permutations of n:          O(n * n!)   - n! perms, each copied in O(n)
# Combination sum (target T): O(T^n / n!) worst case without pruning
# N-Queens:                   O(n!)       - prune reduces practical count

# For n=10 permutations: 10! = 3,628,800 paths
import math
n = 10
print(f'n={n}: n!={math.factorial(n):,} paths')
print(f'n={n}: 2^n={2**n:,} subsets')

Backtracking-Probleme erkennen

# Common backtracking problem types:
# 1. Subsets / Power set
# 2. Permutations (with/without duplicates)
# 3. Combinations (k from n, combination sum)
# 4. Grid path finding (word search, unique paths with visited tracking)
# 5. Constraint satisfaction (N-queens, Sudoku solver)
# 6. String partitioning (palindrome partition, word break all)

# Template reminder:
def backtrack(start, path):
    # base case: add to results or return True
    for choice in get_choices(start):
        if is_valid(choice, path):   # prune
            path.append(choice)      # choose
            backtrack(start+1, path) # explore
            path.pop()               # unchoose

def get_choices(start): return []
def is_valid(c, p): return True

Kurzer Test

Zusammenfassung der Lektion