26个月小孩做飞机可以免票吗?# NextGeneration - 我爱宝宝
a*n
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;
}
};
地方可以优化成n-depth+1,就不需要再往后面走了,因为这个解不成立,但是OJ上说
是错的,想了下竟然没想明白。有谁指点一下?
class Solution {
public:
void addComb(int n, int depth, int begin, vector
vector
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
vector
vector
addComb(n, k, 1, res, solution);
return res;
}
};