Share my C++ solution,easy to understand


  • 0
    V
    class Solution {
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int>> ret;
            vector<int> temp;
            
            if (k <= 0 || n <= 0)
                return ret;
            
            dfs(n, 1, k, temp, ret);
            
            return ret;
        }
        
        void dfs(int target, int start, int k, vector<int> temp, vector<vector<int>> &ret)
        {
            if (target < start)
                return;
            
            int i = start, len = 0;
            for (i = start; i <= 9; ++i)
            {
                temp.push_back(i);
                len = temp.size();
                if (target == i && len == k)
                {
                    ret.push_back(temp);
                    return;
                }
                if (target > i && len < k)
                    dfs(target-i, i+1, k, temp, ret);
                
                temp.pop_back();
            }
        }
    };

  • 0
    V

    Compare it with another two similar problems:

    "Combination Sum II":

    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);
    
                temp.pop_back();
    
                while (i+1 < n && candidates[i+1] == candidates[i])
                    ++i;
    
                ++i;
            }
        }
    };
    

    "Combination Sum":

    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.