【练习题】给定两个整数n和k,返回1 ... n中k个数的所有组合
程序员文章站
2022-07-12 08:53:29
...
例:
For example,
If n = 4 and k = 2, a solution is
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
分析题目:例子中,n=4,k=2;
1,2,3,4 两个数一组组合
我们通常的思路就是先选定第一个数,从1开始,然后分别和后面的数组合,1完了,再向后遍历用2去组合
用代码实现也是这个思路
class Solution {
public:
void findCombine(int index, vector<int>& tmp, const int& n, const int& k, vector<vector<int>>& res){
if(tmp.size() == k)//组成一组了,插入到vector
{
res.push_back(tmp);
return;
}
//最主要的代码
for(int i = index; i <= n; i++)
{
tmp.push_back(i);
findCombine(i+1, tmp, n,k, res);
tmp.pop_back();
}
return;
}
vector<vector<int>> combine(int n, int k)
{
vector<vector<int>> res;
if(n < k || n < 1 || k < 1)
return res;
vector<int> tmp;
findCombine(1, tmp, n, k, res);
return res;
}
};
运用了递归、回溯,当凑够一组时,就回退回去,pop掉一个数,在进行组合
在tmp里,2进出,3进出,用了回溯的思想,进行分别与1组合