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);
return 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
answer.add(new ArrayList<>(path));
// 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;}
path.add(candidates[i]);
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);
}
}
```