# 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]]
# Solution
Approach 1: DFS.
# Code (Python)
Approach 1:
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
elements = [_ for _ in range(1, 10)]
result = []
current = []
self._comb_sum(elements, 0, current, k, n, result)
return result
def _comb_sum(self, elements, start, current, num_left, sum_left, result):
if sum_left < 0 or num_left < 0:
return
if num_left == 0:
if sum_left > 0:
return
if sum_left == 0:
result.append([_ for _ in current])
return
for i in range(start, len(elements)):
current.append(elements[i])
self._comb_sum(elements, i + 1, current, num_left - 1, sum_left - elements[i], result)
current.pop()
# Code (C++)
Approach 1:
class Solution {
private:
vector<vector<int>> com;
void tryCombination(vector<int>& buf, int num, int k, int n) {
if (k == 0 && n == 0)
{
com.push_back(buf);
return;
}
if (num <= 9)
{
if (k > 0 && n >= num)
{
buf.push_back(num);
tryCombination(buf, num + 1, k - 1, n - num);
buf.pop_back();
}
tryCombination(buf, num + 1, k, n);
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<int> buf;
tryCombination(buf, 1, k, n);
return com;
}
};