歡迎關注個人公眾號：愛喝可可牛奶
LeetCode演算法訓練-回溯總結
適用問題
- 組合問題：N個數里面按一定規則找出k個數的集合
- 排列問題：N個數按一定規則全排列，有幾種排列方式
- 切割問題：一個字串按一定規則有幾種切割方式
- 子集問題：一個N個數的集合里有多少符合條件的子集
- 棋盤問題：N皇后，解數獨等等
通用模板
result 存放結果集
path 某個符合條件的結果
void backtracking(引數) {
if (終止條件) {
result.add(path);
return;
}
for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
處理節點;
backtracking(路徑，選擇串列); // 遞回
回溯，撤銷處理結果
}
}
個人理解
-
回溯和遞回緊密相聯，有遞回就有回溯
-
回溯的程序可以抽象為一個回溯樹，要搞清楚題目要求的是分支節點、葉子節點、還是所有節點
-
去重 回溯樹的同一個樹枝去重（用全域used陣列） 同一個樹層上去重（for回圈外的區域used陣列）
-
畫回溯樹找條件寫代碼，什么時候要添加結果，什么時候要continue，要不要以及能不能對原始資料集排序
-
剪枝優化 什么情況下不用再遞回樹枝不用遞回樹層，這時可直接在for回圈中給出限制條件
-
回溯函式遍歷樹枝，for回圈++遍歷樹層
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/545273.html
標籤：Java
下一篇：設計模式