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

    private void dfs(List<Integer> list, int sum, int cur, List<List<Integer>> res, int k, int n) {
        if (cur > 9 || list.size() == k) {
            if (list.size() == k && sum == n) res.add(list);
            return;
        }
        dfs(list, sum, cur + 1, res, k, n);
        List<Integer> newlist = new ArrayList<Integer>(list);
        newlist.add(cur);
        dfs(newlist, sum + cur, cur + 1, res, k, n);
    }
}