# Time Complexity of dynamic programming vs recursion?

• As the title says, what should be the time complexity of using dynamic programming vs recursion? At first glance, I think dp is polynomial time while recursion may use up to exponential time, however, I implemented in both ways and found out dp solution takes more time.

The following are my recursive and dp solutions:

dp:

``````  public class Solution {
class Result {
List<List<Integer>> res;

Result() {
res = new ArrayList<List<Integer>>();
}

}
}

public List<List<Integer>> combinationSum2(int[] num, int target) {
Arrays.sort(num);
Result[][] DP = new Result[target+1][num.length+1];
for (int i=0; i<=target; i++) {
DP[i][num.length] = new Result();
}
for (int j=num.length-1; j>=0; j--) {
int candi = num[j];
for (int i=0; i<=target; i++) {
DP[i][j] = new Result();
if (i>0 && i < candi) continue;
for (int k=0; k<= (i >= candi ? 1 : 0); k++) {
int t = j+1;
if (k==0) {
while (t < num.length && num[t] == candi) t++;
}
for (List<Integer> comb : DP[i-k*candi][t].res) {
if (k > 0)
}
}
}
}
return DP[target][0].res;
}
}
``````

recursive:

``````public List<List<Integer>> combinationSum2(int[] num, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> current = new ArrayList<Integer>();
Arrays.sort(num);
combinationSum2(result, current, num, 0, target);
return result;
}

private void combinationSum2(List<List<Integer>> result, List<Integer> current,
int[] num, int startIdx, int target) {
if (target == 0) {
return;
}

if (startIdx >= num.length || num[startIdx] > target) {
return;
}

if (target >= num[startIdx]) {