## Combination Sum III

07/16/2016 Array Backtracking

## Question

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.

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]]


## Solution

Result: Accepted Time: 0 ms

Here should be some explanations.

class Solution {
public:
void dfs(int rest,int st,int k,vector<vector<int>> &vec,vector<int> &ivec)
{
if(!rest && !k)
return vec.push_back(ivec);
int limit = (2*st+k-1)*k/2;
if(k == 1) st = rest;
for(int i = st; limit <= rest && i < 10; i++,limit +=k)
{
ivec.push_back(i);
dfs(rest - i,i+1,k-1,vec,ivec);
ivec.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> vec;
vector<int> ivec;//(k);
dfs(n,1,k,vec,ivec);
return vec;
}
};


Complexity Analytics

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$