1.理論基礎(chǔ)

題目鏈接/文章講解：代碼隨想錄

視頻講解：帶你學(xué)透回溯算法（理論篇）| 回溯法精講！_嗶哩嗶哩_bilibili

來自代碼隨想錄的網(wǎng)站：

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

所以回溯法，都可以轉(zhuǎn)換成一個n叉樹的樹形結(jié)構(gòu)，集合的大小就是子樹的寬度 ，遞歸的深度就是樹的深度。

2.組合

題目鏈接/文章講解： 代碼隨想錄

視頻講解：帶你學(xué)透回溯算法-組合問題（對應(yīng)力扣題目：77.組合）| 回溯法精講！_嗶哩嗶哩_bilibili

剪枝操作：帶你學(xué)透回溯算法-組合問題的剪枝操作（對應(yīng)力扣題目：77.組合）| 回溯法精講！_嗶哩嗶哩_bilibili

代碼：（未剪枝）?

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(int n,int k,int startIndex){// 遞歸返回條件if(path.size() == k){result.push_back(path);return;}// 遍歷n叉樹里的結(jié)點for(int i = startIndex;i <= n;i++){path.push_back(i);backtracking(n,k,i + 1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return result;}
};

代碼：（剪枝版）

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(int n,int k,int startIndex){// 遞歸返回條件if(path.size() == k){result.push_back(path);return;}// 遍歷n叉樹里的結(jié)點for(int i = startIndex;i <= n - (k - path.size() - 1);i++){path.push_back(i);backtracking(n,k,i + 1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return result;}
};

思路：剪枝的情況就是，我們所能選擇的數(shù)值的數(shù)目已經(jīng)小于提上要求的組合大小，這種情況可以剪掉。

以前for循環(huán)里，i <=n ,現(xiàn)在，我們要求出剩余數(shù)字的數(shù)目不少于n的開始下標(biāo)，即 n - (k - path.size() - 1)。這里用總數(shù)目減去已經(jīng)用過的數(shù)字個數(shù)，即 k - path.size() - 1。減1，是因為我們開始時的下標(biāo)為1，已經(jīng)默認用了一個元素了。

其實這種套模板的題，還是很省腦的（什么？