題目鏈接
tag:
- Medium；
question：
??Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解法一：
思路：這道題讓求1到n共n個(gè)數(shù)字里k個(gè)數(shù)的組合數(shù)的所有情況扣泊，還是要用深度優(yōu)先搜索DFS來(lái)解，根據(jù)以往的經(jīng)驗(yàn)尺上，像這種要求出所有結(jié)果的集合，一般都是用DFS調(diào)用遞歸來(lái)解抽米。那么我們建立一個(gè)保存最終結(jié)果的大集合res狞谱，還要定義一個(gè)保存每一個(gè)組合的小集合out，每次放一個(gè)數(shù)到out里免糕，如果out里數(shù)個(gè)數(shù)到了k個(gè)赢乓，則把out保存到最終結(jié)果中，否則在下一層中繼續(xù)調(diào)用遞歸说墨。網(wǎng)友u010500263的博客里有一張圖很好的說(shuō)明了遞歸調(diào)用的順序骏全，請(qǐng)點(diǎn)擊這里苍柏。根據(jù)上面分析尼斧，可寫(xiě)出代碼如下：
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> out;
helper(n, k, 1, out, res);
return res;
}
void helper(int n, int k, int level, vector<int>& out, vector<vector<int>>& res) {
if (out.size() == k) {res.push_back(out); return;}
for (int i = level; i <= n; ++i) {
out.push_back(i);
helper(n, k, i + 1, out, res);
out.pop_back();
}
}
};
解法二：
思路：我們?cè)賮?lái)看一種迭代的寫(xiě)法，也是一種比較巧妙的方法试吁。這里每次先遞增最右邊的數(shù)字棺棵，存入結(jié)果res中，當(dāng)右邊的數(shù)字超過(guò)了n熄捍，則增加其左邊的數(shù)字烛恤，然后將當(dāng)前數(shù)組賦值為左邊的數(shù)字，再逐個(gè)遞增余耽，直到最左邊的數(shù)字也超過(guò)了n缚柏，停止循環(huán)。對(duì)于n=4, k=2時(shí)碟贾，遍歷的順序如下所示：
0 0 #initialization
1 0
1 1
1 2 #push_back
1 3 #push_back
1 4 #push_back
1 5
2 5
2 2
2 3 #push_back
2 4 #push_back
...
3 4 #push_back
3 5
4 5
4 4
4 5
5 5 #stop
代碼如下：
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> out(k, 0);
int i = 0;
while (i >= 0) {
++out[i];
if (out[i] > n) --i;
else if (i == k - 1) res.push_back(out);
else {
++i;
out[i] = out[i - 1];
}
}
return res;
}
};
