c++ dfs solution


  • 0
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        vector<vector<int>> result;
        vector<int> line;
        
        sort(candidates.begin(), candidates.end());
        dfs(result, line, 0, candidates, target);
        
        return result;
    }
    
    void dfs(vector<vector<int>>& result, vector<int>& line, int start, vector<int> candidates, int target)
    {
        if (target <= 0)
        {
            if (target == 0)
                result.push_back(line);
            return;
        }
        for (int i = start; i < candidates.size(); i++)
        {
            if (i > start && candidates[i] == candidates[i - 1])
                continue;
            line.push_back(candidates[i]);
            dfs(result, line, i + 1, candidates, target - candidates[i]);
            line.pop_back();
        }
    }

Log in to reply
 

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