s*****n
发帖数: 994 | 1 不知道什么地方可以改进？请有时间的朋友指点一下
combinationsum1用类似的办法就没超时
class Solution {
public:
vector > combinationSum2(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort (num.begin(), num.end());
vector > results(0);
addOneBit(num, target, results);
return results;
}
void addOneBit (vector &num, int target, vector > &
results){
if (target == 0){
vector empty;
results.push_back(empty);
return;
}else if (num.size() <= 0){
return;
}
/*if (accumulate(num.begin(), num.end(), 0) < target){
return;
}*/
int ele = num.back();
num.pop_back();
int counter = 1;
while (num.back() == ele){//eliminate dupes
num.pop_back();
counter++;
}
vector > temp(0);
for (int i=0; i<=counter; ++i){
addOneBit (num, target-i*ele, results);
vector tail(i,ele);
for (int j=0; j
results[j].insert(results[j].end(), tail.begin(), tail.end()
);
}
temp.insert(temp.end(), results.begin(), results.end());
results.clear();
}
results = temp;
for (int i=1; i<=counter; ++i){
num.push_back(ele);
}
return;
}
}; | s*****n
发帖数: 994 | 2 self fixed, add
{if target<0 return}
【在 s*****n 的大作中提到】
: 不知道什么地方可以改进？请有时间的朋友指点一下
: combinationsum1用类似的办法就没超时
: class Solution {
: public:
: vector > combinationSum2(vector &num, int target) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: sort (num.begin(), num.end());
: vector > results(0);
: addOneBit(num, target, results);
| l*******b
发帖数: 2586 | 3 呵呵呵。。。。
【在 s*****n 的大作中提到】
: self fixed, add
: {if target<0 return}
|
|
