C++, DFS specially designed to avoid duplicate dfs-tree-path


  • 0
    A
    Solution {
    public:
        vector<vector<int>> res;
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<int> temp;
            DFS_combination(candidates, temp, 0, target);
            return res;
        }
        void DFS_combination(vector<int>& cand, vector<int> &temp, int loc, int target){
            if(target==0) res.push_back(temp);
            for(int i=loc; i<cand.size() && cand[i]<=target; i++){
                if(i>loc && cand[i]==cand[i-1]) continue;
                // code above is to avoid constructing duplicate path, where
                // for-loop will try to construct tree node with i in sequence, 
                // so we should ensure that i will not duplicate.
                temp.push_back(cand[i]);
                DFS_combination(cand, temp, i+1, target-cand[i]);
                temp.pop_back();
            }
        }
    };
    

    In this case, we need to deal with duplicates during DFS, what matters is to analyse where harmful duplicates will occur.


Log in to reply
 

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