题目

题解

class Solution {
    List < List<Integer> > result = new ArrayList<>();  // 存放结果集
    LinkedList<Integer> path = new LinkedList<>(); // 符合条件的结果
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(n,k,0,1);
        return result;
    }
    public void backtracking(int n, int k, int sum, int startIndex ) {
        int size = path.size();
        if(sum > n ) { // 剪枝操作 
            return ; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        if(k == size ) {
            if(sum == n) {
                result.add(new ArrayList<>(path));
            }
            return ;
        }
        for(int i = startIndex; i <= 9 -(k - size ) + 1; i++ ) { //剪枝
            sum += i;
            path.add(i);
            backtracking(n,k,sum,i+1);
            sum -= i;
            path.removeLast();
        }
    }
}