# DFS + backtracking

• 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)

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