# C++ DP solution but time exceeded.

• class Solution {

public:

``````vector<vector<int>> result;

vector<int> middleResult;

void combinationSum2Generating (vector<int>& candidates, int target, int start, int end) {

if (target == 0) {

result.push_back(middleResult);

} else {

// guess + resursion

for (int i = start; i < end; i++) {

middleResult.push_back(candidates[i]);

combinationSum2Generating(candidates, target-candidates[i], i+1, end);

middleResult.pop_back();

}

}

}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

combinationSum2Generating(candidates, target, 0, candidates.size());

return result;

}
``````

};

• Any one could help ? why it is time-exceeded ?

• I tested this on coderPad, and the result is correct.

• class Solution {
public:
vector<vector<int>> result;
vector<int> temp;

``````void combinationSum2_sub (vector<int>& candidates,
int target,
int start,
int end) {

if (target == 0) {
if (find(result.begin(), result.end(), temp) == result.end()) {
result.push_back(temp);
}
return;
}

if (target < candidates[start]) {
return;
}

for (int i = start; i<end; i++) {
temp.push_back(candidates[i]);
combinationSum2_sub(candidates, target-candidates[i], i+1, end);
temp.pop_back();
}
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// sort the array
sort(candidates.begin(), candidates.end());
combinationSum2_sub(candidates, target, 0, candidates.size());
return result;
}
``````

};

• you need to cut down on the extra cases, like if the sum > target, then stop processing further

• class Solution {
public:
vector<int>temp;
vector<vector<int> >result;

``````vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());

sumHelper(candidates,target,0,candidates.size());
return result;
}

void sumHelper(vector<int>& candidates,int target,int index,int length){
//index代表数组索引值，length代表数组长度
if(target==0){
//这里很巧的是，别人用sum求和，他不用，他是相减，只要等于0了，就会存入数组中。
if(find(result.begin(),result.end(),temp)==result.end()){
result.push_back(temp);
}
return;//不需要返回
}
if(index>=length||target<0){//因为是求减法，如果不相等，立即返回||
//还有一种是索引值大于数组长度
return;
}

for(int i=index;i<=length-1;i++){
temp.push_back(candidates[i]);
sumHelper(candidates,target-candidates[i],i+1,length);
temp.pop_back();
}
}
``````

};

• @laputa This is NOT DP! This is just simple recursive.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.