class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(k, n, 1, new ArrayList<>());
return ans;
}
private void dfs(int k, int sum, int cur, List<Integer> path) {
if (sum == 0) {
if (k == 0 && cur <= 10) {
ans.add(new ArrayList<>(path));
}
return;
}
if (k <= 0 || sum < 0 || cur >= 10) {
return;
}
dfs(k, sum, cur + 1, path);
path.add(cur);
dfs(k - 1, sum - cur, cur + 1, path);
path.remove(path.size() - 1);
}
}