回溯法就是「系統化地試所有可能」。跟暴力的差別？暴力是傻試，回溯會在發現走不通時提前回頭（剪枝）。排列、組合、子集、N 皇后——全是這個套路。
先講結論
回溯法的模板就三行：做選擇 → 遞迴 → 撤銷選擇。排列、組合、子集的差別只在「怎麼控制不重複」。搞懂這個模板，你就能解七八成的回溯題。
模板
void backtrack(路徑, 選擇列表) {
if (滿足結束條件) {
result.add(路徑的副本);
return;
}
for (選擇 : 選擇列表) {
if (!isValid(選擇)) continue; // 剪枝
path.add(選擇); // 做選擇
backtrack(路徑, 選擇列表); // 遞迴
path.remove(last); // 撤銷選擇
}
}關鍵是最後那行「撤銷選擇」。遞迴回來之後，你要把狀態還原，才能嘗試下一個選擇。忘記這行 = bug。
排列 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 左右），它完全夠用。
回溯法教你一個人生道理：走錯路不可怕，可怕的是走錯了還不回頭。剪枝教你另一個：有些路根本不用走，用看的就知道是死路。