> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/backtracking/216.-combination-sum-iii.md).

# 216. Combination Sum III

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.

**Note:**

* All numbers will be positive integers.
* The solution set must not contain duplicate combinations.

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

```cpp
vector<vector<int>> combinationSum3(int k, int n) { // time: O(C(9, k)); space: O(C(9, k))
    vector<vector<int> > res;
    vector<int> cur;
    helper(res, cur, k, n, 1);
    return res;
}
void helper(vector<vector<int> >& res, vector<int>& cur, int k, int n, int start) {
    if (k == 0 && n == 0) {
        res.push_back(cur);
    } else if (k == 0 || n == 0) {
        return;
    } else {
        for (int i = start; i <= 9 && i <= n; ++i) {
            cur.push_back(i);
            helper(res, cur, k - 1, n - i, i + 1);
            cur.pop_back();
        }
    }
}
```