C++ 19ms backtracking solution PogChamp


  • 0
    I
    class Solution {
    public:
        void dfs(int target, vector<int>& candidates, int start, vector<int> temp, vector<vector<int>>& res) {
            if (target == 0) {
                res.push_back(temp);
                return;
            }
            for (int i = start; i < candidates.size(); i++) {
                if (i != 0 && candidates[i] == candidates[i - 1]) continue;
                int n = target - candidates[i];
                if (n >= 0) {
                    temp.push_back(candidates[i]);
                    dfs(n, candidates, i, temp, res);
                    temp.pop_back();
                }
            }
            return;
        }
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            unordered_map<int, bool> map;
            vector<vector<int>> res;
            vector<int> temp;
            dfs(target, candidates, 0, temp, res);
            return res;
        }
    };
    

Log in to reply
 

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