Clean three solutions in C++


  • 3

    Along with Further optimised Memoization solution

    class Solution {
    private:
        unordered_map<int, int> map;
    public:
        int combinationSum4(vector<int>& nums, int target) {
            if(nums.empty() || target<0) return 0;
            if(target == 0) return 1;
            if(map.count(target)) return map[target];
            long count = 0;
            for(int i = 0; i < nums.size(); ++i)
                count += combinationSum4(nums, target-nums[i]);
            return map[target] = count;
        }
    };
    

    Using array instead of map accelerating the time from 20ms to 8ms.

    class Solution {
    private:
        int arr[100000];
    public:
        Solution() 
        { 
            arr[0] = 1;
            for(int i = 1; i < 100000; ++i) arr[i] = -1;
        }
        int combinationSum4(vector<int>& nums, int target) {
            if(nums.empty() || target<0) return 0;
            if(target == 0) return 1;
            if(arr[target] != -1) return arr[target];
            long count = 0;
            for(int i = 0; i < nums.size(); ++i)
                count += combinationSum4(nums, target-nums[i]);
            return arr[target] = count;
        }
    };
    

    Further optimised DP solution

    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) 
        {
            int arr[target+1]{1, 0};
            for(int i = 1, size = nums.size(); i <= target; ++i)
                for(int j = 0; j < size; ++j)
                    if(i>=nums[j]) arr[i] += arr[i-nums[j]];
            return arr[target];
        }
    };
    

  • 1

    Further optimised DP solution

    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) 
        {
            int arr[target+1]{1, 0};
            for(int i = 1, size = nums.size(); i <= target; ++i)
                for(int j = 0; j < size; ++j)
                    if(i>=nums[j]) arr[i] += arr[i-nums[j]];
            return arr[target];
        }
    };
    

  • 1

    Along with Further optimised Memoization solution

    class Solution {
    private:
        unordered_map<int, int> map;
    public:
        int combinationSum4(vector<int>& nums, int target) {
            if(nums.empty() || target<0) return 0;
            if(target == 0) return 1;
            if(map.count(target)) return map[target];
            long count = 0;
            for(int i = 0; i < nums.size(); ++i)
                count += combinationSum4(nums, target-nums[i]);
            return map[target] = count;
        }
    };
    

  • 1

    Using array instead of map accelerating the time from 20ms to 8ms.

    class Solution {
    private:
        int arr[100000];
    public:
        Solution() 
        { 
            arr[0] = 1;
            for(int i = 1; i < 100000; ++i) arr[i] = -1;
        }
        int combinationSum4(vector<int>& nums, int target) {
            if(nums.empty() || target<0) return 0;
            if(target == 0) return 1;
            if(arr[target] != -1) return arr[target];
            long count = 0;
            for(int i = 0; i < nums.size(); ++i)
                count += combinationSum4(nums, target-nums[i]);
            return arr[target] = count;
        }
    };
    

Log in to reply
 

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