代码随想录 | 刷题-回溯算法1
77. 组合
虽然runtime离谱地高，但是俺居然自己寻思出了怎么回溯，可喜可贺：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<vector<int>> res;
void comb(vector<int> curNums, int l, int r,int k){
if(curNums.size() == k){
res.push_back(curNums);
return;
}
// for(int i = l; i<= r;i++){// 能想明白l和r的关系我已经很不容易了
for(int i = l; i<= r-(k-curNums.size())+1;i++){
// 👆 看了题解发现我想不明白的地方（i最大取多少）应该每次循环重新算而不是代入递归，用于剪枝
curNums.push_back(i);
comb(curNums, i+1, r, k);
curNums.pop_back();// 最重要的一句
}
return;
}
vector<vector<int>> combine(int n, int k) {
vector<int> cur;
comb(cur, 1, n, k);
return res;
}
};O(n * 2^n)
🚩实际代码做的事情：
这段代码实现的是 从 1 到 n 中选择
k 个数的所有组合，即 组合数 C(n,
k)。
所以：
✅ 正确时间复杂度是：
\(O(C(n, k) \cdot k)\)
解释如下：
一共会生成 \(C(n, k)\) 个组合，每个组合长度是
k每次
curNums达到长度k就复制一次curNums到结果res中每次复制
k个元素，因此时间复杂度为 \(O(k)\)总时间复杂度为： \(O(C(n, k) \cdot k)\)
❓那为什么会看到
O(n * 2^n) 的说法？
这个复杂度常出现在子集枚举问题（power set）中，比如“所有子集”或“子集和”等问题，使用类似回溯结构但允许选择/不选择每个元素，即二叉树结构：
1 | for (int i = l; i <= r; i++) { |
选出来的每个子集的长度是从1到n的，而本题组合问题选出来的组合长度固定为K
216.组合总和III
和上题基本思想差不多，多了一些限制条件 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
vector<vector<int>> result;
void comb(vector<int> nums, int k, int l, int n){
if(k == 0){
if(n == 0){
result.push_back(nums);
return;
}else{
return;
}
}
int r = min(9, n);
for(int i = l; i<=r;i++){
nums.push_back(i);
comb(nums, k-1,i+1, n-i);
nums.pop_back();
}
return;
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> nums;
comb(nums,k,1,n);
return result;
}
};
17.电话号码的字母组合
注意终止条件是索引数加一 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public:
const string digToStr[10] = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
vector<string> result;
void comb(string str, string digits, int ind){
if(ind == digits.size()){
result.push_back(str);
return;
}
int d = digits[ind] - '0';
ind++;
string s = digToStr[d];
for(char c : s){
str.push_back(c);
comb(str, digits, ind);
str.pop_back();
}
return;
}
vector<string> letterCombinations(string digits) {
string str;
if(digits.empty())return result;
comb(str, digits, 0);
return result;
}
};
*
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。 *
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算
可以达到