Leetcode: Combination Sum III

216. Combination Sum III

My Submissions

Total Accepted: 20030 Total Submissions: 61524 Difficulty: Medium

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Array Backtracking

Hide Similar Problems

 (M) Combination Sum

````````````````````````````````````````````````````````````````````

BackTracking:

similar as Combination Sum I, and II. 

///////////////////////////////////////////

//codes

class Solution {

public:

    void backTrac(vector<int>& source, vector<int> tmp, vector<vector<int>>& res, int len, int i, int target, int sum, int k){

        if(sum==target && len==k) {res.push_back(tmp); return;}

        else if(sum>target || len>k) return;

        else{

            for (;i<source.size(); i++){

                len+=1;

                sum+=source[i];

                tmp.push_back(source[i]);

                if(len>k)return;

                if(sum>target)return;

                backTrac(source,tmp,  res,  len,  i+1,  target, sum, k);

                sum-=source[i];

                tmp.pop_back();

                len--;

            }

            return;

        }

    }

    vector<vector<int>> combinationSum3(int k, int n) {

        //check input

        //if()

        vector<vector<int>> res;

        vector<int> tmp;

        vector<int> source={1, 2,3,4,5,6,7,8,9};

        int len=0,i=0,target=n, sum=0;

        backTrac(source,tmp,  res,  len,  i,  target, sum, k);

        return res;

    }

};

revised:

//////////////////////////////////////////////
class Solution {
public:
void BT(int k, int n, int i, vector<vector<int>> &res, vector<int> tmp, vector<int> &nums){
if(k==1){
for(int j=i;j<nums.size();j++){
if(nums[j]==n){
tmp.push_back(nums[j]);
res.push_back(tmp);
tmp.pop_back();
return;
}
else if(nums[j]>n){
return;
}

}
}
else{
for(int j=i;j<nums.size();j++){
tmp.push_back(nums[j]);
BT(k-1, n-nums[j], j+1, res, tmp, nums);
tmp.pop_back();
}

}
}


    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
vector<int> tmp, nums={1,2,3,4,5,6,7,8,9};
BT(k, n, 0, res, tmp, nums);
return res;
    }

};