cpp solution for follow up based on memorization search


  • 0
    Z

    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;
    }

Log in to reply
 

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