Time complexity: ?? could not figure it out myself

Running Time: beat 74.28%

Code:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

vector<int> combination;

vector<vector<int>> combinations;

int sum = 0;

std::sort(candidates.begin(), candidates.end());

recursion(0, candidates, target, combination, combinations);

return combinations;

}

```
void recursion(int k, vector<int>& candidates, int target, vector<int>&combination, vector<vector<int>>& combinations) {
if (target < 0) {
return;
}
if(target == 0) {
combinations.push_back(combination);
return;
}
for(int i = k; i < candidates.size(); i++) {
if (i != k && (candidates[i] == candidates[i - 1])) continue;
combination.push_back(candidates[i]);
recursion(i + 1, candidates, target - candidates[i], combination, combinations);
combination.pop_back();
}
}
```

Algorithm

this follow-up problem can also be solve by basic idea of my post "https://discuss.leetcode.com/topic/80503/dfs-backtracking". A little difference here is we should care duplicate combination (vertex) because the array can have duplicate elements. After drawing out a graph(tree) in the case of duplicate elements, we can see duplicate combinations only can happen when they have same direct parent. so we can eliminate the duplicates when we are exploring neighbors of a combination(vertex)