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.

Example:

1
2
3
4
5
Input: k = 3, n = 7
Output: [[1,2,4]]

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

combination: 还是从start开始，并不是都从0开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, new ArrayList<>(), 1, k, n);
        return list;
    }
    
    public void dfs(List<List<Integer>> list, List<Integer> arr, int start, int k, int n) {
        if (k == 0 && n != 0) return;
        else if (n == 0 && k != 0) return;
        else if (k == 0 && n == 0) list.add(new ArrayList<>(arr));
        else {
            for (int i = start; i <= 9; ++i) {
                arr.add(i);
                dfs(list, arr, i+1, k-1, n - i);
                arr.remove(arr.size() - 1);
            }
        }
    }
}