遞歸-回溯

本文參考自代碼隨想錄視頻：

https://www.bilibili.com/video/BV1cy4y167mM

https://www.bilibili.com/video/BV1ti4y1L7cv

遞歸+回溯理論基礎

只要有遞歸，就會有回溯，遞歸函數的下面的部分通常就是回溯的邏輯。
回溯是純暴力的搜索，有時可以通過剪枝做一些優化。

回溯搜索解決的常見問題

組合問題
切割問題
子集問題
排列問題
棋盤問題

如何理解回溯搜索

所有的回溯法都可以抽象為一個樹形結構（n叉樹）

回溯法模版

回溯函數一般是無返回值的遞歸函數 backtracking，其參數通常較多，我們可以在寫邏輯的時候根據需要來添加參數
終止條件：在回溯遞歸函數中，到了終止條件時，通常就是我們收集結果的時候了
單層搜索的邏輯：通常是一個 for-loop，處理集合的每一個元素，在循環體中處理節點，再進行遞歸調用，然后再撤銷掉處理節點的操作（即所謂回溯）。

以下用偽代碼的形式將上述模板寫出來：

void backtracking(...) {if (終止條件) {收集結果;return;}for (集合中的元素) {處理節點;backtracking(...); // 遞歸調用撤銷處理節點的操作; 		// 回溯}
}

LeeCode相關習題

77. 組合

如果我們未曾接觸過回溯算法，遇到本題的暴力做法會是怎樣做呢，很容易想到，就是嵌套 k 層 for-loop，當 k 是 2 的時候，這也是可行的，但是當 k 是 50 的時候呢，我們發現，即使想要暴力做，程序也不好寫了。

這時就考慮到我們的遞歸-回溯算法，遞歸中的每一層其實就是一層 for 循環，這樣我們就可以自動地去嵌套。


class Solution {
private:void backtracking(vector<vector<int>>& res, vector<int>& curr, int pos, int n, int k) {if (curr.size() == k) {res.push_back(curr);return;}// for (int i=pos; i<n-(k-curr.size()+1; ++i)for (int i=pos; i<=n; ++i) {curr.push_back(i);backtracking(res, curr, i+1, n, k);curr.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> curr;backtracking(res, curr, 1, n, k);return res;}
}

pos表示本次遞歸調用起始的位置，res存放最終的全部組合結果，curr存放當前正在搜索的組合結果。

剪枝：注意到當 i 小于 n-(k-curr.size()) + 1 時，當前就已經不可能得到長度為 k 的結果了，故可以調整 for 循環的范圍，實現剪枝。代碼中注釋掉的 for 循環實際上就是剪枝的版本。注意：遞歸回溯算法在很多時候都是通過合理地減小 for 循環的范圍來實現剪枝的。

另一種角度

另一種角度：每遍歷到一個元素，我們可以選擇將它加入結果或跳過它。

78. 子集

class Solution {
private:void backtracking(vector<vector<int>>& res, const vector<int>& nums, vector<int>& curr, int pos) {if (pos == nums.size()) {res.push_back(curr);return;}// 跳過當前元素backtracking(res, nums, curr, pos+1);// 添加當前元素curr.push_back(nums[pos]);backtracking(res, nums, curr, pos+1);curr.pop_back();}
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;vector<int> curr;backtracking(res, nums, curr, 0);return res;}
};