DFS + backtracking


  • 0
    N

    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)


Log in to reply
 

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