这题这么简单也好意思标中等吗?
这题的朴素写法:
for(int a = 1; a <= n; a++){ for(int b = a + 1; b <= n; b++){ for(int c = b + 1; c <= n; c++){ ...// 总共 k 层for循环 { int res[] = {a, b, c, ...}; if(res 合法){ ans.emplace_back(res); } } } } }
当然你不可能穷举 k 然后写 k 种 k 层循环啊,所以你要用递归。
class Solution { vector<vector<int>> ans; vector<int> res; int n, k; void search(int start, int layer){ if(layer == k) { ans.emplace_back(res); return; } for(int i = start; i <= layer + n - k + 1; i++){ res[layer] = i; search(i + 1, layer + 1); } } public: vector<vector<int>> combine(int N, int K) { n = N; k = K; res.resize(k, 0); search(1, 0); return ans; } };
当然呢,这个代码 layer + n - k + 1 是做了点优化,如果看不懂,你也可以用个没优化的写法:
void search(int start, int layer){ if(layer == k) { ans.emplace_back(res); return; } if(start > n){ return; } for(int i = start; i <= n; i++){ res[layer] = i; search(i + 1, layer + 1); } }
时间似乎也没多多少,可能是测试用例的关系吧。
然后介绍一个代码量比较少的写法:
class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> ans; vector<int> res(k,0); int layer = 0; while (layer >= 0) { res[layer]++; if(res[layer] > n) layer--; else if(layer == k - 1) ans.emplace_back(res); else{ layer++; res[layer] = res[layer - 1]; } } return ans; } };
这其实就是打包了一下回溯算法,当下层遍历完之后,本层自增 1,直到本层遍历完为止,继续返回上层,让上层自增 1,如此类推,直到第一层也从 1 到 n 遍历完了,返回结果。
但是这个算法好看是好看,没优化过,运行时间略逊一筹。