leetcode combinationsum2 超时# JobHunting - 待字闺中
s*n
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
);
}
temp.insert(temp.end(), results.begin(), results.end());
results.clear();
}
results = temp;
for (int i=1; i<=counter; ++i){
num.push_back(ele);
}
return;
}
};
combinationsum1用类似的办法就没超时
class Solution {
public:
vector
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort (num.begin(), num.end());
vector
addOneBit(num, target, results);
return results;
}
void addOneBit (vector
results){
if (target == 0){
vector
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
for (int i=0; i<=counter; ++i){
addOneBit (num, target-i*ele, results);
vector
for (int j=0; j
);
}
temp.insert(temp.end(), results.begin(), results.end());
results.clear();
}
results = temp;
for (int i=1; i<=counter; ++i){
num.push_back(ele);
}
return;
}
};
