# cpp solution for follow up based on memorization search

• In order to allow negative numbers, the size of the sequence must have a upperbound. Otherwise the result will INF.

My solution used dp idea but since we don't know the exact max sum and min sum can be reached, I can't create a real 2D dptable, I use the memorization search from top down. The cons of this solution is that if the len is too high, stackoverflow might happen.

``````class Solution {
public:
int combinationSum4(vector<int>& nums, int target,int len) {
dptable[0][0]=1;
//sort(nums.begin(),nums.end());
int sum=0;
for(int l=0;l<=len;l++) sum+=dp(nums,target,l);
return sum;
}

int dp(vector<int>& nums,int target,int len){
//first check if this has been searched before
if(dptable.find(len)!=dptable.end() && dptable[len].find(target)!=dptable[len].end()){
return dptable[len][target];
}
else{
if(len==0){
auto entry = dptable[0];
if(entry.find(target)==entry.end()) entry[target]=0;
return entry[target];
}
dptable[len][target]=0;

for(int num:nums){
dptable[len][target]+= dp(nums,target-num,len-1);
//cout<<dptable[len][target]<<endl;
}

return dptable[len][target];
}

}
private:
unordered_map<int,unordered_map<int,int>> dptable;

};
int main() {
std::cout << "Hello, World!" << std::endl;
vector<int> nums{1,2,3,-1};
Solution s;
cout<< s.combinationSum4(nums,4,4);
return 0;
}``````

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