C++ solution, using backtracking, 0ms


  • 0
    Z
    class Solution {
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int> > res;
            if(k>9 || k<1 || n>(19-k)*k/2 || n<(k+1)*k/2) return res;
            if(k==1){
                vector<int> tempVec;
                tempVec.push_back(n);
                res.push_back(tempVec);
                return res;
            }
            
            vector<int> val(k,1);
            int i=0;
            while(val[0]<=n/k){
                if(val[i]<10+i+1-k){
                    i++;
                    if(i==k-1){
                        int temp=n-sumVec(val,k-2);
                        if(temp<10 && temp>val[k-2]){
                            vector<int> tempVec;
                            for(int j=0;j<k-1;j++)
                            tempVec.push_back(val[j]);
                            tempVec.push_back(temp);
                            res.push_back(tempVec);
                        }
                        i--;
                    }
                    val[i]++;
                    //to avoid the value being larger than the values behind it  
                    int j=i;
                    while(j<k-1 && val[j]>val[j+1])
                    {
                        j++;val[j]=val[i];
                    }
                }
                else{
                    if(i==0) break;
                    //to avoid missing some cases
                    for(int j=i;j<k;j++)
                    val[j]=val[i-1]+1;
                    i--; val[i]++;
                }
            }
            return res;
        }
        
        int sumVec(vector<int> nums,int m){
            int sum=0;
            for(int i=0;i<=m;i++)
            sum+=nums[i];
            return sum;
        }
    };

Log in to reply
 

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