cpp solution for follow up based on memorization search

  • 0

    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 {
        int combinationSum4(vector<int>& nums, int target,int len) {
        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];
                auto entry = dptable[0];
                if(entry.find(target)==entry.end()) entry[target]=0;
                return entry[target];
            for(int num:nums){
                dptable[len][target]+= dp(nums,target-num,len-1);
            return dptable[len][target];
    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;

Log in to reply

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