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

• 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];
}
}
``````

• @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];
}
};
``````

• @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.

• @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;
}
};
``````

• @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.

• @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.

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