# Time Complexity Analysis of Recursive Approach

• On the first thought, the time complexity analysis of this brute force approach looks difficult. We are going through each elements and calling recursively on each of those elements. Is it n ^ n ?

The fact that we are doing brute force gives us the answer of complexity. If you think, we are essentially selecting all possible subsets of of set.

{1,2,3} -> {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

There are 2 ^n such elements and hence the time complexity is O(2^n)

Example:
It is easy to see this with example also. We select input that will explore all the paths such as {1,2,3,4,5,6,7} and the target is big enough so it will not prune any path. It will call the iteration 128 times.

``````public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {

List<List<Integer>> answer = new ArrayList<>();
if(candidates == null || candidates.length == 0){return answer;}

// Sort the array, it is needed to take care of duplicates and effective pruning
Arrays.sort(candidates);

dfs(0, candidates, target, new ArrayList<>(), answer);
}

private static int complexity = 0;

private void dfs(int index, int candidates[], int target, List <Integer> path, List<List<Integer>> answer){
if(target == 0){
// The path gives us answer
// Return back as numbers after this will be bigger and will not give us answer
return;
}

complexity ++;

for(int i = index; i < candidates.length; i++){

// Avoid visiting duplicate elements
if(i != index && candidates[i] == candidates[i-1]){ continue; }

// This element and all that will appear after this are too big
if(target - candidates[i] < 0){break;}

dfs(i + 1, candidates, target-candidates[i], path, answer);

path.remove(path.size()-1);
}
}
public static void main(String[] args) {
System.out.println(new Solution().combinationSum2(new int []{1,2,3,4,5,6,7}, 1000));
System.out.println(complexity);
}
}
``````

• Actually, I think for the time complexity it should be the sum of C(n, n) + C(n, n - 1) + C(n, n - 2) + C(n, n - 3) + .... + C(n, 1) ~= n^n

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