# Evolve from recursion to dp

1. Recursion O(n^(target/min(nums))
``````    int combinationSum4(vector<int>& nums, int target) {
if(target<=0) return !target?1:0;
int ct=0;
for(int i=0;i<nums.size();i++) ct+=combinationSum4(nums, target-nums[i]);
return ct;
}
``````
1. memoization O(n*target)
``````    int combinationSum4(vector<int>& nums, int target) {
vector<int> mem(target+1,-1);
return dfs(target,mem,nums);
}
int dfs(int target, vector<int>& mem, vector<int>& nums) {
if(target<=0) return !target?1:0;
if(mem[target]!=-1) return mem[target];
int ct=0;
for(int i=0;i<nums.size();i++) ct+=dfs(target-nums[i],mem,nums);
return mem[target] = ct;
}
``````
1. dp O(n*target), This is slower than memoization because memorization does not compute all from 1 to target.
``````    int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1);
dp[0]=1;
for(int i=1;i<=target;i++)
for(int j=0;j<nums.size();j++)
if(i >= nums[j]) dp[i] += dp[i-nums[j]];
return dp[target];
}
``````
1. dp O(n*target), early termination
``````    int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1);
dp[0]=1;
sort(nums.begin(),nums.end());
for(int i=1;i<=target;i++)
for(int j=0;j<nums.size();j++)
if(i >= nums[j]) dp[i] += dp[i-nums[j]];
else break;
return dp[target];
}
``````

• Hi
I was wondering why is the complexity O(2^(target/min(nums))
At each node, we can recurse `n` times..
And we can go as deep as `target`..
Thus, it might be O(n^target).
Of course, your bound is much tighter and I was wondering how did you derive that

Thanks

• @henry19 You are right. It is a typo O(2^(target/min(nums)) should be O(n^(target/min(nums)). Thanks for picking it out

Can you please explain how the runtime complexity approach 2 (recursion with memoization) is `O(n*target)`?