题目链接：Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
这道题的要求是给定2个整数n和k，返回1…n中所以k个数的组合。
由于要输出所以情况，因此可以考虑递归回溯输出所有情况。依次固定每一个数字作为开始，然后递归处理后面的数字即可。递归的时候逐层递减k，因此递归结束条件就是k等于1，此时需要记录该种情况。
其中b为生成组合的起始数字。
时间复杂度：O(???)（结果数量）
空间复杂度：O(???)（结果数量）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
vector<vector<int> > combine(int n, int k)
{
vector<int> vi;
combine(n, k, vi, 1);
return vvi;
}
private:
vector<vector<int> > vvi;
void combine(int n, int k, vector<int> &vi, int b)
{
if(k == 1)
vvi.push_back(vi);
else
for(int i = b; i <= n + 1 - k; ++ i)
{
vi.push_back(i);
combine(n, k - 1, vi, i + 1);
vi.pop_back();
}
}
};
也可以事先按k的大小开出数组，这样可以减少push_back和pop_back的重复调用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
vector<vector<int> > combine(int n, int k)
{
vector<int> vi(k);
combine(n, k, vi, 1);
return vvi;
}
private:
vector<vector<int> > vvi;
void combine(int n, int k, vector<int> &vi, int i)
{
while(i <= n)
{
vi[vi.size() - k] = i ++;
if(k == 1)
vvi.push_back(vi);
else
combine(n, k - 1, vi, i);
}
}
};