Share my C++ solution, easy to understand


  • 0
    V
    class Solution {
    public:
        vector<vector<int>> combinationSum(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, temp, ret);
            
            return ret;
        }
        
        void dfs(vector<int>& candidates, int target, int start, vector<int> temp, vector<vector<int>> &ret) 
        {
            int n = candidates.size(), i = 0;
            if (target < candidates[start])
                return;
            
            for (i = start; i < n; i++)
            {
                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, temp, ret);
                    
                temp.pop_back();
            }
        }
    };

Log in to reply
 

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