回溯法就是「系統化地試所有可能」。跟暴力的差別？暴力是傻試，回溯會在發現走不通時提前回頭（剪枝）。排列、組合、子集、N 皇后——全是這個套路。
回溯就是走不通就退回去
回溯法的模板就三行：做選擇 → 遞迴 → 撤銷選擇。排列、組合、子集的差別只在「怎麼控制不重複」。搞懂這個模板，你就能解七八成的回溯題。
模板
void backtrack(路徑, 選擇列表) {
if (滿足結束條件) {
result.add(路徑的副本);
return;
}
for (選擇 : 選擇列表) {
if (!isValid(選擇)) continue; // 剪枝
path.add(選擇); // 做選擇
backtrack(路徑, 選擇列表); // 遞迴
path.remove(last); // 撤銷選擇
}
}關鍵是最後那行「撤銷選擇」。遞迴回來之後，你要把狀態還原，才能嘗試下一個選擇。忘記這行 = bug。
把這個模板攤開來看，其實就是在一棵「決策樹」上做 DFS。以全排列 [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]每往下一層就是「做一個選擇」，走到葉子收一組答案，而「撤銷選擇」就是沿著邊往上退回岔路口、換隔壁那條路走。剪枝，講白了就是在某個節點直接判定「這條分支底下不可能有答案」，整棵子樹連踏都不踏。
排列 vs 組合 vs 子集
| 問題 | [1,2,3] 的結果 | 去重方式 |
|---|---|---|
| 排列 | [1,2,3], [1,3,2], [2,1,3]… (6個) | used[] 陣列 |
| 組合 C(3,2) | [1,2], [1,3], [2,3] (3個) | start 參數 |
| 子集 | [], [1], [1,2], [1,2,3]… (8個) | start 參數 |
排列：每個位置都可以放任何未用過的元素
void permute(int[] nums, boolean[] used, List<Integer> path) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
permute(nums, used, path);
path.remove(path.size() - 1);
used[i] = false;
}
}組合：只能往後選（避免重複）
void combine(int n, int k, int start, List<Integer> path) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return;
}
// 剪枝：剩餘元素不夠就不選了
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
combine(n, k, i + 1, path);
path.remove(path.size() - 1);
}
}子集：每個節點都是答案
void subsets(int[] nums, int start, List<Integer> path) {
result.add(new ArrayList<>(path)); // 不用等到葉子
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
subsets(nums, i + 1, path);
path.remove(path.size() - 1);
}
}三個問題的程式碼結構幾乎一樣，差別只在迴圈起點和收集答案的位置。
剪枝：回溯法的靈魂
不剪枝的回溯就是暴力搜尋。剪枝讓你跳過「肯定不行」的分支。
常見剪枝技巧：
- 排序 + 跳過重複：
nums[i] == nums[i-1]時 skip - 餘量不足：剩餘元素不夠填滿結果
- 超過限制：當前和已經超過 target，後面的（排序後更大）肯定也超過
好的剪枝可以把指數級的搜尋空間砍掉大半。
N 皇后：回溯法的招牌題
4 皇后的一個解：
. Q . .
. . . Q
Q . . .
. . Q .放 queen 時檢查三個方向：同列、左上對角線、右上對角線。一旦衝突就剪枝。
檢查衝突：
queens[row] = col
同列：queens[i] == col
對角線：|queens[i] - col| == |i - row|4 皇后有 2 組解，8 皇后有 92 組解。暴力要檢查 N^N 種放法，剪枝後實際搜尋空間小非常多。
回溯的時間複雜度
| 問題 | 複雜度 |
|---|---|
| 全排列 | O(n!) |
| 組合 C(n,k) | O(C(n,k)) |
| 子集 | O(2^n) |
| N 皇后 | O(n!) |
指數級或階乘級。回溯法本質上就是暴力搜尋的優化版，不要期待多項式時間。但在搜尋空間不大的問題上（n < 20 左右），它完全夠用。
🎬 互動視覺化：遞迴家族三兄弟 — 把回溯跟遞迴、分治擺一起跑，看「做選擇 → 遞迴 → 撤銷」在決策樹上一步步走進去又退回來的過程。
回溯法教你一個人生道理：走錯路不可怕，可怕的是走錯了還不回頭。剪枝教你另一個：有些路根本不用走，用看的就知道是死路。
接下來往哪走
- Divide and Conquer 分治法 — 下一篇：同樣靠遞迴，但子問題彼此獨立、不用回頭
- 2)) — 剪枝救不了的指數搜尋空間，折半枚舉還有一線生機
- LeetCode 刷題路線：從 Easy 到 Hard 的跨主題推進地圖 — Subsets → Permutations → N-Queens 的刷題順序在這裡