216. Combination Sum III

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        int[] number = new int[]{1,2,3,4,5,6,7,8,9};
        List<Integer> cur = new ArrayList<>();
        helper(k, n, 0, number, cur, res);
        return res;
    }
    
    private void helper(int k, int n, int index, int[] number, List<Integer> cur, List<List<Integer>> res) {
        if (cur.size() == k && getSum(cur) == n) {
            res.add(new ArrayList<>(cur));
            return;
        }
        if (cur.size() > k) {
            return;
        }
        if (getSum(cur) > n) {
            return;
        }
        for (int i = index; i < number.length; i++) {
            cur.add(number[i]);
            helper(k, n, i + 1, number, cur, res);
            cur.remove(cur.size() - 1);
        }
    }
    
    private int getSum(List<Integer> cur) {
        int sum = 0;
        for (int num : cur) {
            sum += num;
        }
        return sum;
    }
}