Why static array cannot be used here in C++?


  • 2

    The Memorization solution here is intuitive but using static array make the latter calculation corrupt (using map in class is okay).

    Using static array is not cool.

    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            if(nums.empty() || target<0) return 0;
            if(target == 0) return 1;
            static vector<int> map(100000, -1);
            map[0] = 1;
            if(map[target] != -1) 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 map just get accepted.

    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

    B.T.W. Someone knows how to initialise a static array using -1 here? Thanks in advance!


  • 1

    Currently I'm using class member to handle it as follows.

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

    But I really do not enjoy it.


Log in to reply
 

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