目錄

• • 1、題目
  • 2、回溯法思路
  • 3、參考其他思路，更深入了解這個問題
  • 4、剪枝優化

可能需要回顧到的知識文章：
1、常用算法總結(窮舉法、貪心算法、遞歸與分治算法、回溯算法、數值概率算法)
2、回溯法初步
刪除vector容器中的對象元素的三種方法:pop_back, erase與remove算法

1、題目

給定兩個整數 n 和 k，返回 1 … n 中所有可能的 k 個數的組合。

2、回溯法思路

集合元素個數為n，由此可以看出解空間樹每個結點有n孩子，深度為k。
利用模板，就就就AC了。。。
每次確定一個起點和一個終點，從start遍歷到end（對于本層元素而言）。
將第i個元素放入res中，然后進入下一層，下一層的起點是i+1(這樣start只會一直向大的數值延伸，不會產生重復的元素)。
如果不符合就把這個元素pop掉。

class Solution {
public:vector<vector<int>> result;vector<int> res;void backtracking(int start,int end,int k){//找到了k個數if(res.size() == k){result.push_back(res);return;}for(int i=start;i<=end;i++){//處理結點；res.push_back(i);//遞歸,探索下一層backtracking(i+1,end,k);		//遞歸//回溯，撤銷處理結果res.pop_back();}}vector<vector<int>> combine(int n, int k) {result.clear();res.clear();backtracking(1,n,k);return result;}
};

3、參考其他思路，更深入了解這個問題

對于較小的k，我們可以很容易想到for循環嵌套k層解決，如下：
n=4,k=2;

int n = 4;
for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {cout << i << " " << j << endl;}
}

但是對于較大的k，我們的顯然不能寫嵌套for。例如要解決n=100.k=50的情況，暴力寫法需要嵌套50層for循環，而回溯法就是利用遞歸來解決嵌套層數的問題。
每一層遞歸中嵌套一個for循環，那么遞歸就可以用于解決多層嵌套循環的問題了。
觀察我們的解空間樹：

每次從集合中選取元素，可選擇的范圍隨著選擇的進行而收縮，調整可選擇的范圍。
n相當于樹的寬度，k相當于樹的深度。

4、剪枝優化

下面的遍歷范圍是可以剪枝優化的：

for(int i=start;i<=end;i++)
{//處理結點；res.push_back(i);//遞歸,探索下一層backtracking(i+1,end,k);		//遞歸//回溯，撤銷處理結果res.pop_back();
}

舉例n=4,k=4時，那么第一層for循環的時候，從元素2開始的遍歷就已經沒有意義了，因為遍歷了也湊不到4個元素了。
所以我們可以剪枝的地方就是每一層的end。
我們已經選擇的元素個數為：res.size()
我們還需要的元素的個數為k-res.size()
所以最多從end-(k-res.size())+1的地方開始遍歷。
所以可以修改為：

for(int i=start;i<=end-(k-res.size())+1;i++)
{//處理結點；res.push_back(i);//遞歸,探索下一層backtracking(i+1,end,k);		//遞歸//回溯，撤銷處理結果res.pop_back();
}

完整代碼：

class Solution {
public:vector<vector<int>> result;vector<int> res;void backtracking(int start,int end,int k){//找到了k個數if(res.size() == k){result.push_back(res);return;}for(int i=start;i<=end-(k-res.size())+1;i++){//處理結點；res.push_back(i);//遞歸,探索下一層backtracking(i+1,end,k);		//遞歸//回溯，撤銷處理結果res.pop_back();}}vector<vector<int>> combine(int n, int k) {result.clear();res.clear();backtracking(1,n,k);return result;}
};

可以看到速度是有明顯的提升的：