一:題目

給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。

你可以按 任何順序 返回答案。

示例 1：

輸入：n = 4, k = 2 輸出： [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ] 示例 2：輸入：n = 1, k = 1 輸出：[[1]]

二：思路

強調組合：{1,2},{2,1} 這兩個是等價的

思路：
1.經典回溯算法題，我們正常來思考這道題的時候 如果 k = 2,我們可能會用兩層for循環來解決
但如果 k 一直往上增加 那么就要套k層循環 如此的話，是不合理的所以要用到遞歸回溯
2.這里選擇的解的空間依然是 排列樹 因為逐層往下的分支樹木減少
（第一層 1 2 3 4）
（第二層 2 3 4）
（第三層3 4）
（第四層 4）
3.在這里我們選取for循環來遍歷給定的容器里的元素，縱向是backstacking()遞歸尋求結果 到達葉
節點 這里也就是遞歸結束的時候將結果存在另一個容器當中。
4.具體寫碼
1>:遞歸函數的返回值和參數
返回值:vector<vector > res :用來存最后的結果
vector path ：用來存每次的求取的結果
backtracking(n,k,index):這里的 n 和 k就是題目中給出的參數
需要注意的是 這里的 index 是需要記錄我們每次的都是在不斷縮小范圍的

2>:回溯終止條件

當path.size() == k的時候這時容器中的元素已經裝滿了這是就是遞歸終止的條件

3>:單層的搜索過層 即
for循環來遍歷給定的容器里的元素，縱向是backstacking()遞歸尋求結果 到達葉
節點

三：上碼（未剪枝優化的）

class Solution { public:vector<vector<int> > res;vector<int> path;void backtracking(int n,int k,int index){if(path.size() == k){res.push_back(path);return;}for(int i = index; i <= n ; i++){path.push_back(i);backtracking(n,k,i+1);//每次往下遞歸的時候使不斷縮小范圍的path.pop_back();//這里是處理每次遞歸到葉節點是時候 這時已經處理好一種可行解，那么就要為下一種// 可行解提供空間}}vector<vector<int>> combine(int n, int k) {/**思路：1.經典回溯算法題，我們正常來思考這道題的時候 如果 k = 2,我們可能會用兩層for循環來解決但如果 k 一直往上增加 那么就要套k層循環 如此的話，是不合理的所以要用到遞歸回溯2.這里選擇的解的空間依然是 排列樹 因為逐層往下的分支樹木減少 （第一層 1 2 3 4） （第二層 2 3 4）（第三層3 4）（第四層 4）3.在這里我們選取for循環來遍歷給定的容器里的元素，縱向是backstacking()遞歸尋求結果 到達葉節點 這里也就是遞歸結束的時候將結果存在另一個容器當中。4.具體寫碼1>:遞歸函數的返回值和參數返回值:vector<vector<int> > res :用來存最后的結果vector<int> path ：用來存每次的求取的結果 backtracking(n,k,index):這里的 n 和 k就是題目中給出的參數需要注意的是 這里的 index 是需要記錄我們每次的都是在不斷縮小范圍的 2>:回溯終止條件 當path.size() == k的時候這時容器中的元素已經裝滿了這是就是遞歸終止的條件3>:單層的搜索過層 即 for循環來遍歷給定的容器里的元素，縱向是backstacking()遞歸尋求結果 到達葉節點 */backtracking(n,k,1);return res;} };

四：剪枝

在這里我們考慮的是當 n = k的時候 只需要for循環的第一層就足夠了 因為再往下就都不符合條件因為 剩下的元素個數已經不夠 k個了
這里我們需要在 backtacking()中的for循環做如下更改：

for(int i = index; i <= n - (k - path.size()) + 1; i++)

這里建議舉個例子理解 n - (k - path.size()) + 1;

比如 n = 4,k = 3,那么剛開始的時候 path.size() = 0, 那么接下來的話， 4 - （3 - 0）+ 1 = 2，
我們可以得知即可以的for循環也就兩次 （i 是從1開始的）
（1，2，3）和（2，3，4）

總結

以上是生活随笔為你收集整理的77. 组合016(回溯法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。