递归与回溯

递归三要素

终止条件：最小子问题直接返回。

递归关系：大问题化为规模更小的同类问题。

返回值与含义：单值、布尔、或路径收集。

斐波那契教学用递归，面试要补记忆化或递推，避免重复子问题爆炸。

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

回溯通用模板

在决策树的每条从根到叶的路径上，依次做选择：

def backtrack(path, options):
    if 满足结束条件:
        result.append(path[:])  # 拷贝
        return
    for choice in options:
        if 不合法(choice):
            continue
        path.append(choice)
        更新状态(choice)
        backtrack(path, 下一层选项)
        path.pop()
        恢复状态(choice)

子集（元素可选可不选）：每层从 start 开始枚举，避免重复组合。

def subsets(nums):
    res, path = [], []
def dfs(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1)
            path.pop()
dfs(0)
    return res

排列、组合与去重

• 组合 C(n,k)：start 只增，保证 [1,2] 与 [2,1] 不重复。
• 排列：需要 used 数组；有重复元素时先排序，同一层 if i > start and nums[i]==nums[i-1]: continue（组合）或 !used[i-1] 规则（排列）。

N 皇后：按行放皇后，列上检查列、主副对角冲突（用集合或位运算），放不下则剪枝。

复杂度与面试表达

回溯最坏常指数级，面试要说清分支因子与剪枝效果。答题步骤：画决策树 → 写 path/used → 写终止与收集 → 写剪枝条件 → 提空间为递归深度 O(n)。

经典题：46、47、78、39、40、51、79（网格 DFS 亦同「四方向回溯」）。网格题注意 visited 与回溯还原，避免重复访问同一格。