LeetCode演算法訓練-回溯總結

歡迎關註個人公眾號：愛喝可可牛奶

LeetCode演算法訓練-回溯總結

適用問題

• 組合問題：N個數裡面按一定規則找出k個數的集合
• 排列問題：N個數按一定規則全排列，有幾種排列方式
• 切割問題：一個字元串按一定規則有幾種切割方式
• 子集問題：一個N個數的集合里有多少符合條件的子集
• 棋盤問題：N皇後，解數獨等等

通用模板

result 存放結果集
path 某個符合條件的結果
void backtracking(參數) {
    if (終止條件) {
        result.add(path);
        return;
    }
    
    for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
        處理節點;
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結果
    }
}

個人理解

1. 回溯和遞歸緊密相聯，有遞歸就有回溯

2. 回溯的過程可以抽象為一個回溯樹，要搞清楚題目要求的是分支節點、葉子節點、還是所有節點

3. 去重 回溯樹的同一個樹枝去重（用全局used數組） 同一個樹層上去重（for迴圈外的局部used數組）

4. 畫回溯樹找條件寫代碼，什麼時候要添加結果，什麼時候要continue，要不要以及能不能對原始數據集排序

5. 剪枝優化 什麼情況下不用再遞歸樹枝不用遞歸樹層，這時可直接在for迴圈中給出限制條件

6. 回溯函數遍歷樹枝，for迴圈++遍歷樹層