A simple solution using backtracking without using a set to handle duplicates


  • 2
    A
    class Solution {
    public:
        vector<vector<int> > combinationSum2(vector<int> &num, int target) {
            sort(num.begin(), num.end());
            
            vector<vector<int>> res;
            vector<int> cur;
            int cur_sum = 0;
            backtrack(num, target, 0, res, cur, cur_sum);
            
            return res;
        }
        
        void backtrack(const vector<int> &num, int target, int low,
            vector<vector<int>> &res, vector<int> &cur, int &cur_sum)
        {
            if (cur_sum == target)
            {
                res.push_back(cur);
                return;
            }
            
            if (cur_sum > target)
                return;
                
            for (int i = low; i < num.size(); ++i)
            {
                cur_sum += num[i];
                cur.push_back(num[i]);
    
                backtrack(num, target, i + 1, res, cur, cur_sum);
    
                cur.pop_back();
                cur_sum -= num[i];
                
                //handling duplicates:
                //simply don't start any new combinations with a duplicate
                while (i < num.size() - 1 && num[i + 1] == num[i])
                    ++i;
            }
        }
    };

  • 0
    T

    Your solution is a good example of backtracking! Thanks!


  • 1
    X

    Thanks for handling duplicates part


Log in to reply
 

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