C++ backtracking solution with detailed explanation


  • 29
    L

    At the beginning, I stuck on this problem. After careful thought, I think this kind of backtracking contains a iterative component and a resursive component so I'd like to give more details to help beginners save time. The revursive component tries the elements after the current one and also tries duplicate elements. So we can get correct answer for cases like [1 1] 2. The iterative component checks duplicate combinations and skip it if it is. So we can get correct answer for cases like [1 1 1] 2.

    class Solution {
    public:
        vector<vector<int> > combinationSum2(vector<int> &num, int target) 
        {
            vector<vector<int>> res;
            sort(num.begin(),num.end());
            vector<int> local;
            findCombination(res, 0, target, local, num);
            return res;
        }
        void findCombination(vector<vector<int>>& res, const int order, const int target, vector<int>& local, const vector<int>& num)
        {
            if(target==0)
            {
                res.push_back(local);
                return;
            }
            else
            {
                for(int i = order;i<num.size();i++) // iterative component
                {
                    if(num[i]>target) return;
                    if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination
                    local.push_back(num[i]),
                    findCombination(res,i+1,target-num[i],local,num); // recursive componenet
                    local.pop_back();
                }
            }
        }
    };

  • 0
    W

    for the following line:
    if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination.
    I think you can also write in other words:
    if(i == order || num[i-1] != num[i]){local.push_back(num[i]); findCombination(res,i+1,target-num[i],local,num); local.pop_back();} // with the following 3 lines inside the parenthesis


  • 0
    E

    Thanks a lot!


  • 0

    if there is 1 1 1 2, and how can you get only one [1 ,1] result? could you plz explain?


  • 1
    A

    You don't need else block


  • 0
    S

    @yanchao_hust

    if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination

    this code will help to skip the duplicate.
    BTW,the first condition is unnecessary.Just swap the position of the second condition and the third conditio.


  • 0
    G

    What is the time complexity and space of this code?


  • 5
    W

    Another way:

    vector<vector<int>> combinationSum2(vector<int>& A, int target) {
        vector<vector<int>> res;
        vector<int> path;
        sort(A.begin(), A.end());
        combinationSum2(A, 0, path, target, res);
        return res;
    }
    
    void combinationSum2(vector<int>& A, int pos, vector<int> &path, int target, vector<vector<int>> &res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (pos == A.size() || target - A[pos] < 0) return;
        auto num = A[pos++];
        path.push_back(num);
        combinationSum2(A, pos, path, target - num, res);
        path.pop_back();
        
        while (A[pos] == num) ++pos;
        combinationSum2(A, pos, path, target, res);
    }
    

  • 0
    C

    @yanchao_hust because the array is sorted at the very beginning.


  • 1
    P
    if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination
    

    I kind of get it but can someone explain how does this work to prevent duplicates?
    If i is the same as order, then nums[i] is being included for the first time as a candidate.
    But if i > order, then nums[i] is starting over using a duplicate number. Is this correct?


  • 0
    M

    @wfxr I think this is clearer.


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

    why is it wrong? the result of run is null;


Log in to reply
 

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