Что такое backtracking?

Backtracking — перебор с возвратом: exploration всех возможностей через DFS, отсечение путей, ведущих к неудаче. Шаблон: попробовать выбор, рекурсия, отменить выбор.

def backtrack(state):
    if is_complete(state):
        result.append(state[:])
        return
    for choice in choices(state):
        make(choice)
        backtrack(state)
        undo(choice)

# Permutations (LeetCode 46)
def permute(nums):
    res = []
    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path, used)
                path.pop()
                used[i] = False
    backtrack([], [False] * len(nums))
    return res

Сложность обычно экспоненциальная (O(2ⁿ) или O(n!)). Pruning — отсечение веток, не дающих решения. Memoization для overlapping subproblems → DP. Примеры: N-Queens, Combinations, Subsets, Sudoku Solver.