# Clean three solutions in C++

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

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

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

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