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:

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]]

一刷
题解： BT + DFS

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        comb(1, 9, k, n, res, list);
        return res;
    }
    
    private void comb(int from, int to, int num, int target, List<List<Integer>> res, List<Integer> list){
        if(target<0 || list.size()>num) return;
        if(target == 0 && list.size() == num){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=from; i<=to; i++){
            list.add(i);
            comb(i+1, to, num, target-i, res, list);
            list.remove(list.size()-1);
        }
        
    }
}

二刷
BT + DFS

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        comb(1, 9, res, list, k, n);
        return res;
    }
    
    private void comb(int lo, int hi, List<List<Integer>> res, List<Integer> list, int k, int n){
        if(n<lo) return;
        if(k == 1 && n<10){
            list.add(n);
            res.add(new ArrayList<>(list));
            list.remove(list.size()-1);
            return;
        }
        
        for(int i=lo; i<=hi; i++){
            list.add(i);
            comb(i+1, hi, res, list, k-1, n-i);
            list.remove(list.size()-1);
        }
    }
}