77. 組合 - 力扣（LeetCode）

題目描述

給定兩個(gè)整數(shù)?n?和?k，返回范圍?[1, n]?中所有可能的?k?個(gè)數(shù)的組合。

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

樣例輸入

示例 1：

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

示例 2：

輸入：n = 1, k = 1
輸出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

題解

暴力算法

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

在上述暴力算法中，題目中k等于多少，我們就要嵌套多少個(gè)for循環(huán)，顯然這樣寫代碼是不合理的，而在回溯算法中，我們用遞歸代替嵌套的for循環(huán)

回溯算法

核心

• for循環(huán)的本質(zhì)是遍歷每一層
• 遞歸的本質(zhì)是遍歷每個(gè)深度下的樹枝

核心代碼：

        //橫向遍歷for(int i=startIndex;i<=n;i++){path.emplace_back(i);//處理節(jié)點(diǎn)backing(n,k,i+1,path,res);//縱向遍歷path.pop_back();//回溯}

在上述代碼中，我們用for循環(huán)用來橫向遍歷，遞歸的過程是縱向遍歷。同時(shí)用startIndex控制每層遍歷的起始位置，每往深層下降一層就用path保存取到的節(jié)點(diǎn)i，當(dāng)滿足終止條件return返回到上一層前要進(jìn)行回溯，撤銷處理的結(jié)點(diǎn)。

也就是說，backing（遞歸函數(shù)）通過不斷調(diào)用自己一直往深處遍歷，總會遇到葉子節(jié)點(diǎn)，遇到了葉子節(jié)點(diǎn)就要返回。

那么終止條件是什么呢？很顯然，每當(dāng)我們收集path的過程中path的大小等于k的時(shí)候，就說明我們已經(jīng)收集到了一個(gè)滿足題意的結(jié)果，此時(shí)即可終止本次遞歸，返回上一層，即：

        //遞歸出口if(path.size()==k){res.push_back(path);//收集結(jié)果return;}

?

代碼

class Solution {
public:void backing(int& n,int& k,int startIndex,vector<int>& path,vector<vector<int>>& res){//遞歸出口if(path.size()==k){res.push_back(path);//收集結(jié)果return;}//橫向遍歷，n-(k-path.size())+1為剪枝優(yōu)化for(int i=startIndex;i<=n-(k-path.size())+1;i++){path.emplace_back(i);backing(n,k,i+1,path,res);//縱向遍歷path.pop_back();//回溯}}vector<vector<int>> combine(int n, int k) {vector<int> path;vector<vector<int>> res;backing(n,k,1,path,res);return res;}
};