## Combination Sum III

• Time:O(C(9, k)) = O(9^k)
• Space:O(n)

## C++

``````class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
dfs(k, n, 1, {}, ans);
return ans;
}

private:
void dfs(int k, int n, int s, vector<int>&& path, vector<vector<int>>& ans) {
if (k == 0 && n == 0) {
ans.push_back(path);
return;
}
if (k == 0 || n <= 0)
return;

for (int i = s; i <= 9; ++i) {
path.push_back(i);
dfs(k - 1, n - i, i + 1, move(path), ans);
path.pop_back();
}
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
dfs(k, n, 1, new ArrayList<>(), ans);
return ans;
}

private void dfs(int k, int n, int s, List<Integer> path, List<List<Integer>> ans) {
if (k == 0 && n == 0) {
return;
}
if (k == 0 || n < 0)
return;

for (int i = s; i <= 9; ++i) {
dfs(k - 1, n - i, i + 1, path, ans);
path.remove(path.size() - 1);
}
}
}
``````

## Python

``````class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
ans = []

def dfs(k: int, n: int, s: int, path: List[int]) -> None:
if k == 0 and n == 0:
ans.append(path)
return
if k == 0 or n < 0:
return

for i in range(s, 10):
dfs(k - 1, n - i, i + 1, path + [i])

dfs(k, n, 1, [])
return ans
``````