遞迴與回溯法 — 從遞迴三要素到回溯模板完整教學 | 資料結構與演算法
2026/06/30
遞迴（Recursion） 是函式呼叫自身來分解問題的程式設計技巧；回溯法（Backtracking） 則是在遞迴搜尋樹上系統性地嘗試所有可能解，當發現當前路徑不可能產生合法解時，立即撤銷（unchoose）並換下一條路徑的演算法策略。掌握這兩者，是解決排列、組合、子集、N-Queens 等經典面試題的關鍵。
前言
你有沒有試過打開俄羅斯套娃？打開最外層，裡面還有一個一模一樣形狀的娃娃；打開第二層，又是一個更小的；直到拆到最小那一個，再也打不開了——這就是遞迴最直觀的比喻。
回溯法（Backtracking）則像是在迷宮中探索：每到一個岔路口，你選一條路走進去；若碰壁，原路退回岔路口，再試另一條。這種「走不通就回頭」的策略，正是回溯的精髓。
這兩個概念放在一起，能解決演算法世界裡一大類「窮舉所有可能」的問題。讀完這篇文章，你將能夠：
- 理解遞迴三要素，避免無窮遞迴與堆疊溢出
- 掌握 choose → explore → unchoose 回溯模板，套用到任何搜尋問題
- 實作排列（Permutation）、組合（Combination）、子集（Subset）、N-Queens 四大經典題
- 學會剪枝（Pruning）策略，讓回溯從「暴力搜尋」變成「智慧搜尋」
- 看懂 C++ 位元運算最佳化版本，面試中展示深度
- 對應 LeetCode 46、78、39、51、17 等高頻考題
核心概念一：遞迴三要素
任何正確的遞迴函式都必須同時滿足以下三個條件。少了任何一個，程式就會出錯。
1. Base Case（終止條件）
Base Case 定義最小子問題的答案，阻止函式無限呼叫自身。若缺少 Base Case，call stack 會不斷累積呼叫框架，最終觸發 Stack Overflow。
最典型的例子是計算階乘（Factorial）：
// n! = n × (n-1) × (n-2) × ... × 1
function factorial(n: number): number {
// Base Case：0! = 1，停止遞迴
if (n === 0) return 1;
// 遞迴步驟：n! = n × (n-1)!
return n * factorial(n - 1);
}
console.log(factorial(5)); // 輸出：120
// 呼叫鏈：factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0) = 1
2. 遞迴關係（Recurrence Relation）
遞迴關係定義如何把規模為 n 的問題，拆解為規模更小的相同問題。數學上可用以下三種典型關係表示：
T(n) = T(n-1) + O(1) ← 線性遞迴（如走訪鏈結串列）
T(n) = 2·T(n/2) + O(n) ← 二分遞迴（如 Merge Sort）
T(n) = n·T(n-1) ← 指數遞迴（如全排列）
以費波那契數列（Fibonacci）為例，它的遞迴關係是 F(n) = F(n-1) + F(n-2)：
// 純遞迴版（有重複計算問題，僅作示意）
function fibNaive(n: number): number {
if (n <= 1) return n; // Base Case
return fibNaive(n - 1) + fibNaive(n - 2); // 遞迴關係
}
// 記憶化版本（O(n) 時間，避免重複計算）
function fib(n: number, memo: Map<number, number> = new Map()): number {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n)!;
const result = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, result);
return result;
}
console.log(fib(10)); // 輸出：55
console.log(fib(50)); // 輸出：12586269025（純遞迴版會超時，記憶化版瞬間完成）
3. 收斂性（Convergence）
每次遞迴呼叫都必須讓問題規模嚴格縮小，確保最終能觸及 Base Case。若每次呼叫規模不變甚至增大，即使有 Base Case 也永遠到不了。
// 錯誤示範：規模沒有縮小，無窮遞迴
function badRecursion(n: number): number {
if (n === 0) return 0;
return badRecursion(n); // 錯誤：傳入相同的 n，永遠不會到達 Base Case
}
// 正確：每次呼叫 n 嚴格減少
function goodRecursion(n: number): number {
if (n === 0) return 0;
return goodRecursion(n - 1) + 1; // 正確：n-1 讓問題規模縮小
}
核心概念二：呼叫堆疊視覺化
遞迴執行時，每次函式呼叫都會在呼叫堆疊（Call Stack）上新增一個堆疊框架（Stack Frame），儲存當前函式的局部變數與返回地址。以 factorial(3) 為例：
呼叫階段（向下展開）：
┌─────────────────────┐
│ factorial(0) = 1 │ ← 到達 Base Case，開始返回
├─────────────────────┤
│ factorial(1) │ ← 等待 factorial(0) 的結果
├─────────────────────┤
│ factorial(2) │ ← 等待 factorial(1) 的結果
├─────────────────────┤
│ factorial(3) │ ← 最初呼叫
└─────────────────────┘
返回階段（向上回傳）：
factorial(0) → 1
factorial(1) → 1 × 1 = 1
factorial(2) → 2 × 1 = 2
factorial(3) → 3 × 2 = 6 ← 最終結果
這個結構說明為什麼遞迴深度過深會導致 Stack Overflow：每個框架都佔用記憶體，N 層深度就需要 N 個框架同時存在。
核心概念三：回溯模板 — choose → explore → unchoose
回溯法的核心是三步循環：
function backtrack(狀態, 選擇列表):
if 達到終止條件:
記錄結果
return
for 每個選擇 in 選擇列表:
1. choose — 將選擇加入當前狀態
2. explore — 遞迴進入下一層
3. unchoose — 撤銷選擇，恢復狀態（回溯）
這個模板的關鍵是 unchoose 步驟必須與 choose 步驟完全對稱。做了什麼，就要撤銷什麼，讓下一次迭代從同樣的乾淨狀態出發。
JS/TS 實作
子集（Subsets）— LeetCode 78
子集問題：給定不重複整數陣列 nums，回傳所有可能的子集（包括空集合）。
決策樹邏輯：每個元素有「選」與「不選」兩種決定，總共 2ⁿ 個子集。
以 nums = [1, 2, 3] 為例，組合搜尋樹（k=2, n=4）：
[]
┌───────┬───────┬───────┐
[1] [2] [3] [4]
┌─┼─┐ ┌─┼─┐ └─┐
[1,2][1,3][1,4] [2,3][2,4] [3,4]
✓ ✓ ✓ ✓ ✓ ✓
↑
從 i+1 開始避免重複
// 時間：O(2ⁿ × n) 空間：O(n)（call stack 深度）
function subsets(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
function backtrack(start: number): void {
// 每個節點都是一個合法子集（包含空集合），直接記錄
result.push([...path]); // 必須淺複製！
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose：加入當前元素
backtrack(i + 1); // explore：從 i+1 開始，避免重複
path.pop(); // unchoose：撤銷，回到上一狀態
}
}
backtrack(0);
return result;
}
console.log(subsets([1, 2, 3]));
// 輸出：[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
全排列（Permutations）— LeetCode 46
排列問題：給定不重複整數陣列 nums，回傳所有全排列。
決策樹邏輯：每次從剩餘未使用元素中選一個，共 n! 個排列。
nums = [1, 2, 3] 的全排列決策樹：
[]
┌─────────────┼─────────────┐
[1] [2] [3]
┌──┴──┐ ┌──┴──┐ ┌──┴──┐
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
│ │ │ │ │ │
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
✓ ✓ ✓ ✓ ✓ ✓
總共 3! = 6 個葉節點（合法排列）
// 時間：O(n! × n) 空間：O(n)
function permute(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
const used: boolean[] = new Array(nums.length).fill(false);
function backtrack(): void {
// Base Case：path 已收集所有元素
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue; // 剪枝：已在 path 中的元素跳過
// choose
used[i] = true;
path.push(nums[i]);
// explore
backtrack();
// unchoose（回溯）
path.pop();
used[i] = false;
}
}
backtrack();
return result;
}
console.log(permute([1, 2, 3]));
// 輸出：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
排列 vs 組合的關鍵差異：
| 特性 | 排列（Permutation） | 組合/子集（Combination/Subset） |
|---|---|---|
| 順序 | 重要，[1,2] ≠ [2,1] | 不重要，[1,2] = [2,1] |
| 控制重複 | used[] 陣列，每次從頭掃描 | start 索引，只向後選取 |
| 遞迴參數 | 不傳 start，用 used[] 控制 | 傳 i+1 給下一層 |
組合總和（Combination Sum）— LeetCode 39
組合問題：給定候選數字陣列 candidates 和目標 target，找出所有和等於 target 的組合（元素可重複使用）。
// 時間：O(2^(t/m))，t = target，m = 最小元素值 空間：O(t/m)
function combinationSum(candidates: number[], target: number): number[][] {
const result: number[][] = [];
const path: number[] = [];
// 排序後可進行剪枝：當前元素超過 remaining，後面更大的都跳過
candidates.sort((a, b) => a - b);
function backtrack(start: number, remaining: number): void {
if (remaining === 0) {
result.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
// 可行性剪枝：candidates 已排序，後面的元素只會更大
if (candidates[i] > remaining) break;
path.push(candidates[i]); // choose
backtrack(i, remaining - candidates[i]); // explore（傳 i 而非 i+1，允許重複使用）
path.pop(); // unchoose
}
}
backtrack(0, target);
return result;
}
console.log(combinationSum([2, 3, 6, 7], 7));
// 輸出：[[2,2,3], [7]]
N-Queens — LeetCode 51
N-Queens 問題：在 n×n 棋盤上放置 n 個皇后，使任意兩個皇后不在同一行、列或對角線上。
N-Queens 搜尋樹（n=4，部分展示）：
root
┌──────┬──────┬──────┐
Q在col0 Q在col1 Q在col2 Q在col3
│ │ │ │
row1: row1: row1: row1:
剪枝(對角) [4,2] [4,1] [1,3] ← 合法延伸
↑
剪枝：提早剪掉無效分支
關鍵洞察：
- 同一行（row - col 相同）→ 同一條正對角線
- 同一行（row + col 相同）→ 同一條反對角線
// 時間：O(n!) 空間：O(n)
function solveNQueens(n: number): string[][] {
const result: string[][] = [];
// 使用三個 Set 追蹤列、正對角線、反對角線的衝突
const cols = new Set<number>();
const diag1 = new Set<number>(); // row - col（正對角線）
const diag2 = new Set<number>(); // row + col（反對角線）
const board: number[] = []; // board[row] = col
function backtrack(row: number): void {
// Base Case：所有行都放好皇后
if (row === n) {
result.push(
board.map(col =>
'.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)
)
);
return;
}
for (let col = 0; col < n; col++) {
// 可行性剪枝：同列、正對角、反對角已有皇后
if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
continue;
}
// choose
cols.add(col);
diag1.add(row - col);
diag2.add(row + col);
board.push(col);
backtrack(row + 1); // explore
// unchoose
board.pop();
cols.delete(col);
diag1.delete(row - col);
diag2.delete(row + col);
}
}
backtrack(0);
return result;
}
console.log(solveNQueens(4).length); // 輸出：2（4-Queens 有兩種解法）
電話號碼的字母組合（Letter Combinations）— LeetCode 17
給定手機號碼字串，回傳所有可能的字母組合。
// 時間：O(4^n × n) 空間：O(n)
function letterCombinations(digits: string): string[] {
if (!digits) return [];
const phoneMap: Record<string, string> = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
};
const result: string[] = [];
const path: string[] = [];
function backtrack(idx: number): void {
// Base Case：已處理所有數字
if (idx === digits.length) {
result.push(path.join(''));
return;
}
const letters = phoneMap[digits[idx]];
for (const letter of letters) {
path.push(letter); // choose
backtrack(idx + 1); // explore
path.pop(); // unchoose
}
}
backtrack(0);
return result;
}
console.log(letterCombinations('23'));
// 輸出：['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
C++ 對照實作
全排列含重複元素（Permutations II）— LeetCode 47
C++ 版本搭配排序和重複剪枝，展示如何處理含重複數字的排列問題：
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 排序是重複剪枝的必要前提
backtrack(nums, used, path, result);
return result;
}
private:
void backtrack(
const vector<int>& nums,
vector<bool>& used,
vector<int>& path,
vector<vector<int>>& result
) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < (int)nums.size(); i++) {
if (used[i]) continue;
// 重複剪枝：同一位置不選相同的值
// 條件：前一個相同值「尚未被使用」表示我們在同層選了重複元素
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
path.push_back(nums[i]); // choose
backtrack(nums, used, path, result); // explore
path.pop_back(); // unchoose
used[i] = false;
}
}
};
N-Queens 位元運算最佳化版
C++ 可利用整數位元遮罩（bitmask）替代 Set，速度更快：
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<int> queens(n, -1); // queens[row] = col
// cols、diag1、diag2 各為整數，每個位元代表對應欄位是否被佔用
backtrack(n, 0, 0, 0, 0, queens, result);
return result;
}
private:
void backtrack(
int n, int row,
int cols, int diag1, int diag2, // 位元遮罩
vector<int>& queens,
vector<vector<string>>& result
) {
if (row == n) {
result.push_back(buildBoard(queens, n));
return;
}
// available：此行中沒有衝突的欄位集合
int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
while (available) {
int bit = available & (-available); // 取最低位的可用欄
available &= available - 1; // 清除最低位
int col = __builtin_ctz(bit); // 轉換為欄號
queens[row] = col;
backtrack(
n, row + 1,
cols | bit,
(diag1 | bit) << 1, // 正對角線向下移動（左移）
(diag2 | bit) >> 1, // 反對角線向下移動（右移）
queens, result
);
queens[row] = -1; // unchoose（位元遮罩在遞迴參數中自動恢復）
}
}
vector<string> buildBoard(const vector<int>& queens, int n) {
vector<string> board(n, string(n, '.'));
for (int r = 0; r < n; r++) {
board[r][queens[r]] = 'Q';
}
return board;
}
};
複雜度分析表
| 問題類型 | 時間複雜度 | 空間複雜度（Call Stack） | 說明 |
|---|---|---|---|
| 全排列 Permutation | O(n! × n) | O(n) | n! 個排列，每個長度 n |
| 組合 Combination | O(C(n,k) × k) | O(k) | C(n,k) 個組合 |
| 子集 Subset | O(2ⁿ × n) | O(n) | 每個元素選/不選 |
| N-Queens | O(n!) | O(n) | 每列選一欄，互不衝突 |
| 數獨 Sudoku | O(9^m) | O(m) | m 為空格數，每格最多 9 選擇 |
| 電話號碼字母組合 | O(4^n × n) | O(n) | 最多 4 個字母/數字 |
剪枝策略
剪枝（Pruning）是讓回溯法從「暴力搜尋」變成「智慧搜尋」的核心手段。好的剪枝可以將指數時間大幅壓縮。
可行性剪枝（Feasibility Pruning）
當前狀態已違反問題約束，直接返回，不繼續深入探索：
// 組合總和：candidates 排序後，超過 remaining 就直接 break
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // 可行性剪枝
// ...
}
重複元素剪枝（Duplicate Pruning）
處理含重複元素的問題時，排序後跳過同層中相同值的選擇：
// 子集含重複（LeetCode 90）
function subsetsWithDup(nums: number[]): number[][] {
const result: number[][] = [];
nums.sort((a, b) => a - b); // 必須先排序！
function backtrack(start: number, path: number[]): void {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
// 重複剪枝：同一層（start 相同）中，跳過與前一個相同的值
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}
上界剪枝（Upper-Bound Pruning）
剩餘候選元素數量已不足以填滿所需長度，提前返回：
// 組合（k 個數，從 [1..n] 中選）— 上界剪枝
function combine(n: number, k: number): number[][] {
const result: number[][] = [];
function backtrack(start: number, path: number[]): void {
if (path.length === k) {
result.push([...path]);
return;
}
// 上界剪枝：剩餘可選元素 (n - i + 1) 必須 >= 還需要選的個數 (k - path.length)
for (let i = start; i <= n - (k - path.length) + 1; i++) {
path.push(i);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(1, []);
return result;
}
剪枝策略整理：
| 剪枝類型 | 說明 | 典型場景 |
|---|---|---|
| 可行性剪枝 | 當前狀態已違反約束，直接返回 | N-Queens 衝突檢查、組合超過 target |
| 重複剪枝 | 排序後跳過相同值，避免重複子集 | Combination Sum II、Subsets II |
| 上界剪枝 | 剩餘元素不足，提前返回 | 組合 k 個數問題 |
| 最優性剪枝 | 當前路徑即使走完也比最優解差 | 旅行商問題（TSP） |
面試考點
排列 vs 組合：何時用哪個模板
面試中最常見的混淆點是搞不清楚什麼時候用「start 索引控制」，什麼時候用「used[] 陣列控制」：
- 組合/子集問題（順序不重要）：傳遞
start索引，每層只從start之後選取，天然避免重複 - 排列問題（順序重要）：不傳
start，每層從頭開始掃描，用used[]陣列標記哪些元素已被選入當前路徑
// 組合：i 從 start 開始，避免 [1,2] 和 [2,1] 重複計算
for (let i = start; i < nums.length; i++) { ... }
// 排列：i 永遠從 0 開始，用 used[] 避免同一元素被選兩次
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
...
}
何時應該用回溯法
回溯法適用於以下特徵的問題：
- 需要窮舉所有可能解（排列、組合、子集）
- 約束條件複雜，難以直接計算（N-Queens、數獨）
- 問題可以建模為搜尋樹（每一步有有限選擇，遞迴深度有限）
- 需要找出「是否存在」或「所有」合法路徑
不適合的場景：若問題有最優子結構和重疊子問題，應優先考慮動態規劃（Dynamic Programming）。
常見陷阱
陷阱一：忘記淺複製結果
// 錯誤：推入 path 的引用，後續修改會影響已記錄的結果
result.push(path);
// 正確：推入淺複製
result.push([...path]);
陷阱二：遺漏 unchoose
// 錯誤：只 choose，沒有 unchoose，path 會帶著舊值繼續迭代
path.push(nums[i]);
backtrack(i + 1);
// 忘記 path.pop()！
// 正確：choose 和 unchoose 必須成對出現
path.push(nums[i]); // choose
backtrack(i + 1); // explore
path.pop(); // unchoose ← 不可省略
陷阱三：含重複元素未排序就剪枝
重複剪枝的前提是陣列已排序，否則 nums[i] === nums[i-1] 的比對沒有意義。
LeetCode 練習題
| # | 題目 | 難度 | 核心技巧 | 時間複雜度 |
|---|---|---|---|---|
| 46 | Permutations | Medium | 排列模板 + used[] 陣列 | O(n! × n) |
| 78 | Subsets | Medium | 子集模板，每節點即記錄 | O(2ⁿ × n) |
| 39 | Combination Sum | Medium | 組合模板 + 可行性剪枝 + 允許重複 | O(2^(t/m)) |
| 51 | N-Queens | Hard | 可行性剪枝 + 位元遮罩（C++） | O(n!) |
| 17 | Letter Combinations | Medium | 字元映射 + 回溯，無 used[] | O(4^n × n) |
建議練習順序： 78（子集）→ 46（排列）→ 39（組合）→ 17（電話號碼）→ 51（N-Queens）
這個順序從最基礎的模板出發，逐步加入更多變化：子集讓你理解「每個節點即結果」；排列讓你掌握 used[]；組合加入剪枝；電話號碼驗證字元映射；N-Queens 是最完整的可行性剪枝應用。
總結
遞迴與回溯法是演算法學習中的重要里程碑。我們在這篇文章中涵蓋了：
- 遞迴三要素：Base Case 阻止無窮遞迴、遞迴關係拆解問題、收斂性確保終止
- 回溯模板：choose → explore → unchoose 三步驟，配對出現，不可省略 unchoose
- 四大經典實作：子集（78）、排列（46）、組合總和（39）、N-Queens（51）
- 剪枝策略：可行性剪枝、重複剪枝、上界剪枝，讓暴力搜尋變成智慧搜尋
- C++ 位元運算版本：以整數遮罩取代 Set，提升常數倍效能
- 排列 vs 組合的本質差異：
start索引 vsused[]陣列
理解了這兩個概念，你不只能解出 LeetCode 的回溯題，更能看懂正規表達式引擎的 NFA 回溯、遊戲 AI 的 Minimax 搜尋，乃至拼字檢查器的 Trie 剪枝——它們都是同一個思路的不同應用。
如果這篇文章對你有幫助，歡迎繼續閱讀下一篇：雙指標技巧，我們將深入探索 Two Pointers 在陣列與字串問題中的強大應用。如有任何問題或疑惑，歡迎透過 聯絡頁面 與我交流！