simple c++ solution 0ms


  • 0
    U
    class Solution {
    public:
    int comb(vector<int>& nums, vector<int>& cache, int target)
    {
        if(cache[target] != -1)
        {
            return cache[target];
        }
    
        int cnt = 0;
        for(int i=0; i<nums.size(); i++)
        {
            if(target - nums[i] >= 0)
                cnt +=comb(nums,cache,target-nums[i]);
        }
        cache[target] = cnt;
        return cnt;
    }
    int combinationSum4(vector<int>& nums, int target) {
        vector<int>cache(target+1,-1);
        cache[0] = 1;
        return comb(nums,cache,target);
    }
    };

Log in to reply
 

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