🏗️ 系统设计 / System Design — Day 88 · Expert Synthesis

主题 / Topic: Saturday Deep Dive Week — 回溯与系统设计的交叉点

综合视角 / Synthesis Perspective

今天是 Saturday Deep Dive，重点在回溯算法。系统设计综合思考：

回溯思维在系统设计中的映射 / Backtracking Thinking in System Design:

系统设计本质上也是回溯：你提出一个方案，发现某个约束被违反（延迟太高、成本太贵、扩展性不够），然后"回退"到上一个决策节点，选择另一条路。

具体类比 / Concrete Analogies:

1. 数据库选型 — 选了 SQL → 遇到 schema 变化频繁的问题 → 回退 → 换 NoSQL
2. 缓存策略 — Write-through 发现写延迟不可接受 → 回退 → Write-behind
3. 服务拆分 — 过度微服务化发现运维复杂度爆炸 → 回退 → 合并为模块化单体
4. API 设计 — REST → 发现实时推送需求 → 回退 → 加 WebSocket 层

剪枝的系统设计等价物 / Pruning in System Design:

• "This violates the latency SLA" → prune the branch
• "This exceeds our ops team capacity" → prune
• "CAP theorem: you can't have both strong consistency AND high availability here" → prune

The difference: in coding, backtracking is explicit. In system design, it's called "iterating on the design."

Today's Saturday deep dive covers: backtracking algorithms — Subsets through N-Queens.

💻 算法 / Algorithms — Day 88 · #78 Subsets (Medium) [Backtracking]

🧩 回溯模式 (1/9) — Saturday: Full backtracking guide in today's deep dive

今日题目 / Today's Problem: LeetCode #78 — Subsets

🔗 LeetCode #78 | 📹 NeetCode

核心解法 / Core Solution

def subsets(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(start: int, path: list[int]):
        result.append(path[:])  # collect at every node
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

Time: O(n · 2ⁿ) | Space: O(n)

关键点 / Key Points:

• 每个节点都是合法子集，在每次调用时都收集结果
• start 参数防止重复，确保只向右扩展
• path[:] 浅复制必须有，否则最终结果都是空列表

For the complete backtracking deep dive covering all 5 problem types (Subsets, Combination Sum, Permutations, Subsets II, N-Queens), see today's deep dive archive.

🗣️ 软技能 / Soft Skills — Day 88 · Expert Synthesis

主题 / Topic: Saturday Deep Dive Week — 回溯思维在工程决策中的应用

综合场景 / Synthesis Scenario

场景 / Scenario:

你作为 Staff Engineer 正在主导一个关键系统的重构。你已经推进了 6 周，团队刚刚发现这个方向有一个根本性的问题。如何优雅地"回溯"？

STAR 框架回答模板 / STAR Framework Template:

Situation: 6 weeks into a major architectural refactor, we discovered the new design couldn't meet our latency SLOs due to an unforeseen cross-region call pattern.

Task: I needed to make the call: push forward and try to optimize, or backtrack and rethink the foundation.

Action:

1. Called an emergency design review with the team — no blame, just diagnosis
2. Built a quick proof-of-concept to validate whether optimization was viable (it wasn't)
3. Documented what we'd learned from the 6 weeks — not wasted, it was discovery
4. Proposed a revised design incorporating the new constraints
5. Communicated transparently to stakeholders: "We found a better path, and here's why pivoting now saves us 3 months later"

Result: New design shipped 8 weeks later, 40% faster than the original would have been with patches. Team morale stayed high because I normalized backtracking as learning, not failure.

核心原则 / Core Principle:

在工程中，"回溯"不是失败，是信息积累后的理性决策。好的工程师把它框架为"我们学到了 X，因此现在能做出更好的决定"，而不是"我们浪费了 6 周"。

Saturday deep dive: today's deep dive archive covers backtracking algorithms from Subsets to N-Queens.

🤖 AI 概念 / AI Concept — Day 88 · Expert Synthesis

主题 / Topic: Saturday Deep Dive Week — Synthesis: Backtracking in AI/LLM Systems

AI 系统中的"回溯" / "Backtracking" in AI Systems

回溯算法的思想在现代 AI 系统中有深刻的对应，值得深入思考。

1. Beam Search — LLM 的结构化回溯

当 LLM 生成文本时，贪心解码（每步选最高概率 token）往往不是全局最优。Beam Search 维护 k 个候选序列（beams），类似回溯中同时探索多条路径：

这就是回溯的变体：不是深度优先，而是宽度优先地维护多条路径。

2. Tree of Thoughts — 显式回溯推理

Tree of Thoughts (ToT) 让 LLM 显式地探索推理树，并使用启发式函数来剪枝：

LLM 既是求解器（生成下一步），也是评估器（判断是否值得继续）。

3. AlphaCode / AI 代码生成 — Sample and Filter

AI 代码生成系统大量使用回溯式策略：

1. 生成 N 个候选解（探索）
2. 运行测试用例（评估 / 剪枝）
3. 选择通过率最高的（收集答案）

这比单次生成准确率高出数倍。AlphaCode 生成数千个候选，过滤到最佳。

4. MCTS in Game AI — 蒙特卡洛树搜索

AlphaGo/AlphaZero 使用 MCTS，这是回溯的随机化版本：

• Selection: 沿最有希望的路径向下
• Expansion: 添加新节点
• Simulation: 随机 rollout 到游戏结束
• Backpropagation: 把结果向上传播更新权重

神经网络提供先验概率（剪枝启发式），MCTS 提供搜索结构。

核心洞察 / Core Insight

回溯 = 探索 × 剪枝。 AI 系统在各个层面都在做这件事：

• Token 层：Beam Search
• 推理层：Tree of Thoughts, Chain of Thought with verification
• 代码层：Sample → Test → Filter
• 游戏层：MCTS

理解了回溯，你就理解了很多 AI 推理系统的底层逻辑。

Today's Saturday deep dive covers backtracking in detail: Subsets, Combination Sum, Permutations, Subsets II, and N-Queens.

🔬 Saturday Deep Dive: Backtracking — 回溯算法完全指南 (15 min read)

📊 NeetCode: 70/150 · SysDesign: 60/40 · Behavioral: 60/40 · Frontend: 37/50 · AI: 30/30

🔥 Day 88 — Expert Phase

Overview / 概述

中文：

回溯算法是面试中最常考的算法之一，也是最容易搞混的。它的本质是受控穷举——在搜索树上做深度优先遍历，遇到不满足条件的节点就"剪枝"，回退到上一状态再尝试其他选项。

掌握回溯 = 掌握一个模板 + 一套思维方式。NeetCode 150 中有 9 道回溯题（全在今天开始的这个 block），从今天的 Subsets 到最终的 N-Queens。这篇 deep dive 会让你把模板内化，用一套心智模型解决所有变体。

English:

Backtracking is "controlled brute-force." You explore a decision tree depth-first, undo choices when they lead to dead ends, and continue. The key insight: you're building a result incrementally, and the "undo" step is what makes it backtracking (not just DFS).

This deep dive covers the universal template, 5 core problem types, and the mental model that lets you derive solutions from scratch in interviews.

Part 1: Theory / 理论基础 (5 min)

核心思维模型 / The Mental Model

中文：

把回溯想象成一棵决策树：

• 每个节点代表当前选择路径（path）
• 每条边代表你做的一个选择（"选 or 不选 X"）
• 叶节点是最终答案（完整路径）
• 剪枝：某个分支注定不可能产生有效答案，直接跳过

English:

Think of it as a decision tree:

• Root = empty state
• Each level = one decision
• Leaf = complete valid solution

The "undo" step is critical — it restores state before trying the next branch. Without undo, you'd need to copy state on every call (expensive). With undo, you reuse a single mutable path.

通用模板 / Universal Template

def solve(problem_input):
    result = []
    
    def backtrack(path, start_or_remaining):
        # BASE CASE: path is complete
        if is_complete(path):
            result.append(path[:])  # ← shallow copy! path will mutate
            return
        
        # EXPLORE choices
        for choice in get_choices(start_or_remaining):
            # PRUNE: skip invalid choices early
            if not is_valid(choice, path):
                continue
            
            # CHOOSE
            path.append(choice)
            
            # RECURSE
            backtrack(path, next_state(start_or_remaining, choice))
            
            # UNDO (backtrack)
            path.pop()
    
    backtrack([], initial_state)
    return result

五种变体的关键差异 / 5 Problem Types

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

Problem 1: Subsets (#78) — 基础模板

中文： 给定不含重复元素的整数数组 nums，返回所有可能的子集（幂集）。

English: Return all possible subsets (power set) of a list with no duplicates.

🔗 LeetCode #78 | 📹 NeetCode

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    
    def backtrack(start: int, path: list[int]):
        # Every node in the tree IS a valid subset (including empty)
        # So we collect at EVERY call, not just leaf nodes
        result.append(path[:])  # copy current path
        
        for i in range(start, len(nums)):
            # CHOOSE: add nums[i] to path
            path.append(nums[i])
            
            # RECURSE: only consider elements after i (no duplicates, no reuse)
            backtrack(i + 1, path)
            
            # UNDO: remove nums[i] from path
            path.pop()
    
    backtrack(0, [])
    return result

# Example: nums = [1, 2, 3]
# Decision tree:
#              []
#          /   |   \
#        [1]  [2]  [3]
#       /   \    \
#    [1,2] [1,3] [2,3]
#     /
# [1,2,3]
# Result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

复杂度 / Complexity: Time O(n · 2ⁿ), Space O(n) recursion stack + O(n · 2ⁿ) output

Problem 2: Combination Sum (#39) — 元素可重复使用

中文： 从 candidates 中选数，允许重复使用，找出所有和为 target 的组合。

English: Find all unique combinations that sum to target; each number may be used unlimited times.

🔗 LeetCode #39

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    
    def backtrack(start: int, path: list[int], remaining: int):
        if remaining == 0:
            # COMPLETE: path sums to target
            result.append(path[:])
            return
        if remaining < 0:
            # PRUNE: overshot, no point continuing
            return
        
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            # KEY: pass i (not i+1) → same element can be reused
            backtrack(i, path, remaining - candidates[i])
            path.pop()
    
    backtrack(0, [], target)
    return result

# vs Subsets: start=i (not i+1) allows reuse

Problem 3: Permutations (#46) — 顺序敏感

中文： 返回数组的所有全排列。[1,2] 和 [2,1] 是不同结果。

English: Return all permutations. Order matters: [1,2] ≠ [2,1].

🔗 LeetCode #46

def permute(nums: list[int]) -> list[list[int]]:
    result = []
    used = [False] * len(nums)  # track which elements are in current path
    
    def backtrack(path: list[int]):
        if len(path) == len(nums):
            # COMPLETE: used all elements exactly once
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue  # PRUNE: already in path
            
            # CHOOSE
            used[i] = True
            path.append(nums[i])
            
            # RECURSE: no start param — we consider ALL unused elements
            backtrack(path)
            
            # UNDO
            path.pop()
            used[i] = False
    
    backtrack([])
    return result

# KEY DIFFERENCE from subsets/combinations:
# - No `start` parameter (order matters, can pick from anywhere)
# - Uses `used[]` array instead to avoid duplicates within a path

Problem 4: Subsets II (#90) — 处理重复元素

中文： 数组中有重复元素，要求输出不重复的子集。

English: Array has duplicates; return unique subsets (no duplicate subsets).

🔗 LeetCode #90

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    nums.sort()  # STEP 1: sort so duplicates are adjacent
    result = []
    
    def backtrack(start: int, path: list[int]):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            # STEP 2: skip duplicate at same tree level
            # i > start means we've already explored nums[i-1] at this level
            if i > start and nums[i] == nums[i - 1]:
                continue  # ← the dedup trick
            
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

# nums = [1, 2, 2]
# After sort: [1, 2, 2]
# At level 1:
#   i=0: pick 1 ✓
#   i=1: pick 2 ✓
#   i=2: nums[2]==nums[1] AND i>start → SKIP (would duplicate [2])

去重规则 / Dedup Rule: if i > start and nums[i] == nums[i-1]: continue

• i > start means "we're at the same recursion level" (not going deeper)
• Skip if same value as previous element at this level

Problem 5: N-Queens (#51) — 约束传播

中文： 最经典的回溯题。在 n×n 棋盘上放 n 个皇后，使其互不攻击。

English: Place n queens on n×n board such that no two queens attack each other.

🔗 LeetCode #51

def solveNQueens(n: int) -> list[list[str]]:
    result = []
    # Track which columns and diagonals are occupied
    cols = set()
    pos_diag = set()  # row + col is constant along \ diagonals
    neg_diag = set()  # row - col is constant along / diagonals
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def backtrack(row: int):
        if row == n:
            # COMPLETE: placed queen in every row
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            # PRUNE: this position is under attack
            if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
                continue
            
            # CHOOSE: place queen
            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)
            board[row][col] = 'Q'
            
            # RECURSE: move to next row
            backtrack(row + 1)
            
            # UNDO: remove queen
            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)
            board[row][col] = '.'
    
    backtrack(0)
    return result

# Key insight: one queen per row (we recurse row by row)
# Diagonal detection:
#   pos_diag (↘): cells on same diagonal have equal row+col
#   neg_diag (↗): cells on same anti-diagonal have equal row-col

复杂度 / Complexity: Time O(n!), Space O(n²)

Cross-Check: Verify Diagram vs Code

Let's trace N-Queens with n=4, verifying the constraint sets work correctly:

Diagram and code are consistent — the set-based constraint propagation correctly prunes all attacked positions.

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

1. 忘记复制路径 (Forgetting to copy path)

# WRONG — appends reference to same list
result.append(path)  # ← all entries will be empty [] at the end!

# CORRECT
result.append(path[:])  # shallow copy is fine for flat lists
result.append(list(path))  # equivalent

2. 重复问题不排序 (Skipping sort for duplicates)

• Subsets II, Combination Sum II, Permutations II all require sorting first
• Without sort, duplicates aren't adjacent → dedup logic breaks

3. 收集时机错误 (Wrong collection point)

• Subsets: collect at EVERY call (every node is a result)
• Combination Sum: collect only when remaining == 0
• Permutations: collect only when len(path) == n

4. 组合 vs 排列的 start 参数

# Combination: pass i+1 to avoid reuse, i to allow reuse
backtrack(i + 1, ...)  # no reuse
backtrack(i, ...)      # allow reuse (Combination Sum)

# Permutation: NO start param, use `used[]` instead

5. 提前终止 (Early termination)

# For sorted arrays, if current is already too large, prune the rest
for i in range(start, len(candidates)):
    if candidates[i] > remaining:
        break  # all remaining are larger (since sorted)

Part 4: Real-World Application / 实际应用 (2 min)

中文：

回溯在实际工程中比你想象的更常见：

1. 正则表达式引擎 — .* 匹配时需要回溯尝试不同的匹配长度
2. 编译器解析 — 语法树解析中的回溯文法
3. 约束求解 — Sudoku solvers, scheduling systems, SAT solvers
4. 游戏 AI — Chess, Go 的 minimax 树（带剪枝）
5. 包依赖解析 — pip/npm 解析依赖版本组合

English:

Backtracking powers systems you use daily:

• Regex engines: .* tries all possible lengths, backtracks on mismatch
• SQL query planners: try different join orders, backtrack when cost estimate is poor
• IDE autocomplete: generate candidate completions, prune invalid ones
• Package managers: resolve dependency version combinations (a real combinatorial problem!)
• Constraint solvers: workforce scheduling, exam timetabling

Part 5: Interview Simulation / 面试模拟 (3 min)

面试官： Given Subsets, can you walk me through the decision tree?

你： Sure. We start with an empty path. For [1,2,3], at level 0 we choose whether to include 1: if we do, go left; if not, go right. Then same decision for 2, then 3. Every node (not just leaves) is a valid subset. That's why we collect at every recursive call, not just the base case.

面试官： How would you modify Subsets to handle duplicates like [1,2,2]?

你： Sort the array first, so duplicates are adjacent. Then during the for loop, if i > start and nums[i] == nums[i-1], we skip — this prevents generating duplicate subsets at the same tree level. The i > start condition is crucial: it only skips at the same level, not across levels (which would incorrectly prune [1,2] and [1,2] from different branches).

面试官： What's the time complexity of Permutations?

你： O(n · n!). There are n! permutations; for each, we spend O(n) copying the path into results. The recursion tree has at most n levels, each branching up to n times, but the used[] check ensures we don't revisit — so total nodes = n! (leaf) + n!/1 + n!/2 + ... ≈ O(n · n!).

面试官： When would you use backtracking vs dynamic programming?

你： DP when you need the optimal value of overlapping subproblems. Backtracking when you need to enumerate all valid solutions (or just one). If the problem says "find ALL combinations/permutations/subsets", that's backtracking. If it says "find the MINIMUM cost / MAXIMUM value", lean toward DP first.

面试官： Can you solve Combination Sum without backtracking? (follow-up)

你： You could use iterative BFS with a queue of (current_path, remaining), but it's much less clean and has the same complexity. Backtracking's elegance is in the natural undo via the call stack — the recursive structure mirrors the problem structure. I'd keep it as backtracking.

Summary: The Backtracking Cheat Sheet

CHOOSE what to add to path (loop over choices)
  ↓ PRUNE if invalid (i > start + duplicate, used[], constraint violated)
    ↓ RECURSE (pass new start OR same start for reuse)
      ↓ at base case: result.append(path[:])
    ↑ UNDO: pop from path, unmark used[]

Nine problems this block:

1. #78 Subsets ← today
2. #39 Combination Sum
3. #46 Permutations
4. #90 Subsets II
5. #40 Combination Sum II
6. #79 Word Search
7. #131 Palindrome Partitioning
8. #17 Letter Combinations of Phone Number
9. #51 N-Queens

Internalize the template once. The rest is parameter tuning.