I got a TLE for my answer, could any one help me? Thank you very much!


  • 0
    Y

    Following is my answer. It got an TLE for input [3,33,333] 10000. However, I find the thought of my answer is similar to My 3ms Java DP solution except mine is in a recursive style. Could any one help me figure what is the problem of my answer? Thank you guys so much.

    public class Solution {
        public int combinationSum4(int[] nums, int target) {
            if (nums.length == 0 || nums == null) {
                return 0;
            }
            int[] numOfComb = new int[target + 1];
            numOfComb[0] = 1;
            for (int i = 1; i < target + 1; i++) {
                numOfComb[i] = 0;
            }
            int result = countComb(nums, target, numOfComb);
            return result;
        }
        
        private int countComb(int[] nums, int target, int[] numOfComb) {
            if (numOfComb[target] != 0) {
                return numOfComb[target];
            }
            for (int i = 0; i < nums.length; i++) {
                if (target >= nums[i]) {
                    int nextTarget = target - nums[i];
                    numOfComb[target] += countComb(nums, nextTarget, numOfComb);
                }
            }
            
            return numOfComb[target];
        }
    }
    

  • 1

    @YaokaiYang I've tried that before the solution using recursive or memorization here is not efficient enough. You can try DP instead.

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

  • 1
    Y

    @LHearen Thank you for the bottom-up method. BTW, I finally found out that it is because the big array I created. I changed it to a HashMap which only stores the needed intermediate target and it works fine.
    Thanks to this answer:JAVA recursion solution using HashMap as memory.


  • 0

    @YaokaiYang Thank for your inspiration, I also got my Memoization solution now, though less efficient but easy-understanding.

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

  • 0
    Y

    @LHearen Like what is said in that link, the advantage of a top-down way is that it can prevent from calculating useless cases while in a bottom-up method you have to calculate every sum from 0 to target.


  • 0

    @YaokaiYang Actually that kind of redundancy is ignorable compared to the cost of the recursive invoking and map retrieving. The DP solution in C++ is about 0ms or 4ms while the Memorization will take 20ms is a prove. To my knowledge, the Memoization is always worse than DP in performance but better in readability.


Log in to reply
 

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