前言

?回溯的提出是解決循環問題，回溯的提出就是為了解決排列和組合問題，以及多層遍歷問題，因為如果遍歷的層數越多我們的效率就會越低，回溯加上剪枝能很好解決這個問題。

題目鏈接

77. 組合 - 力扣（LeetCode）

216. 組合總和 III - 力扣（LeetCode）

17. 電話號碼的字母組合 - 力扣（LeetCode）

一、組合

?思路：規定一個路徑集合，和一個結果集合，用if去判斷路徑，用for循環去橫向和縱向去加載路徑。

剪枝優化的思路：去除掉無效的長度。

private:vector<vector<int>> res;vector<int>path;void backtrancing(int n,int k,int startIndex){if(path.size()==k){res.push_back(path);return;}for(int i=startIndex;i<=n;i++){path.push_back(i);backtrancing(n,k,i+1);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {backtrancing(n,k,1);return res;}

private:vector<vector<int>> res;vector<int>path;void backtrancing(int n,int k,int startIndex){if(path.size()==k){res.push_back(path);return;}//剪枝優化一下for(int i=startIndex;i<=n-(k-path.size())+1;i++){path.push_back(i);backtrancing(n,k,i+1);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {backtrancing(n,k,1);return res;}

?

二、組合總和

?思路：

三、電話號碼的字母組合

思路：