a*******n
发帖数: 64 | 1 题很简单，就是从n个数（1到n)里挑出k个数，return所有组合可能。我觉得下面有个
地方可以优化成n-depth+1，就不需要再往后面走了，因为这个解不成立，但是OJ上说
是错的，想了下竟然没想明白。有谁指点一下？
class Solution {
public:
void addComb(int n, int depth, int begin, vector>& res,
vector& solution){
if (depth==0){
res.push_back(solution);
}
for (int i = begin; i <= (n-depth+1); ++i){// i <= n is correct, why
n-depth+1 doesn't work?
solution.push_back(i);
addComb(n, depth-1, i+1, res, solution);
solution.pop_back();
}
return;
}
vector> combine(int n, int k) {
vector> res;
vector solution;
addComb(n, k, 1, res, solution);
return res;
}
}; | s**********g
发帖数: 14942 | 2 不是“错”吧
而是cannot terminate吧
你在
if (depth==0){
res.push_back(solution);
}
这里就该return了
否则depth变成负的，你的(n-depth+1) 超越n，永远跑不完 | a*******n
发帖数: 64 | 3 yes, thanks.
【在 s**********g 的大作中提到】
: 不是“错”吧
: 而是cannot terminate吧
: 你在
: if (depth==0){
: res.push_back(solution);
: }
: 这里就该return了
: 否则depth变成负的，你的(n-depth+1) 超越n，永远跑不完
|
|
