https://leetcode-cn.com/problems/combinations/
最开始可以想到的是回溯法，通过不断递归来生成答案，其时间复杂度为O(K*C(n,k))，解答如下：
需要注意的是可以在回溯的循环中进行剪枝操作i<=n-k+1，因为还需要添加的到结果中的长度为k，所以如果i>n-k+1的话，后面不论再怎么添加，都不可能达到所需的长度，所以可以直接舍去。
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:
void getAll(vector<vector<int>>& result, vector<int>& record, int n, int k, int s) {
for(int i=s; i<=n-k+1; ++i) {
if(k < 1) break;
else if(k == 1) {
vector<int> record_copy(record);
record_copy.push_back(i);
result.push_back(record_copy);
} else {
record.push_back(i);
getAll(result, record, n, k-1, i+1);
record.pop_back();
}
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> record;
getAll(result, record, n, k, 1);
return result;
}
};
|
题目中还有一个很不错的解法https://leetcode-cn.com/problems/combinations/solution/zu-he-by-leetcode/，利用字典序遍历求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> record(k+1);
for(int i=0; i<k; ++i) record[i] = i+1;
record[k] = n+1;
int j = 0;
while(j < k) {
result.push_back(vector<int>(record.begin(), record.begin()+k));
j = 0;
while(j < k && record[j]+1 == record[j+1]) {
record[j] = j+1;
j += 1;
}
record[j] += 1;
}
return result;
}
};
|