Share my C++ solution,easy to understand


  • 0
    V
    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            vector<vector<int>> ret;
            vector<int> temp;
            int n = candidates.size();
            
            if (n == 0)
                return ret;
            
            sort(candidates.begin(), candidates.end());
            dfs(candidates, target, 0, n, temp, ret);
            
            return ret;
        }
        
        void dfs(vector<int>& candidates, int target, int start, int n, vector<int> temp, vector<vector<int>>& ret)
        {
            if (target < candidates[start])
                return;
            
            int i= start, j = 0;
    
            while (i < n)
            {
                temp.push_back(candidates[i]);
                
                if (target == candidates[i])
                {
                    ret.push_back(temp);
                    return;
                }
                else if (target > candidates[i])
                    dfs(candidates, target-candidates[i], i+1, n, temp, ret);
                else
                    return;
                    
                temp.pop_back();
                
                //avoiding duplicate combinations
                while (i+1 < n && candidates[i+1] == candidates[i])
                    ++i;
                    
                ++i;
            }
        }
    };

Log in to reply
 

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