216. 组合总和 III

输入: k = 3, n = 7
输出: [[1,2,4]]

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

 public List<List<Integer>> combinationSum3(int k, int n) {
        int nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        dfs(result, tmp, nums, 0, k, n);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> tmp, int[] nums, int start, int k, int n) {
        if (tmp.size() == k && summ(tmp) == n) {
            result.add(new ArrayList<Integer>(tmp));
        }
        for (int i = start; i < nums.length; i++) {
            tmp.add(nums[i]);
            dfs(result, tmp, nums, i + 1, k, n);
            tmp.remove(tmp.size() - 1);
        }
    }

    private int summ(List<Integer> tmp) {
        if (tmp == null || tmp.size() == 0) {
            return 0;
        }
        int sum = 0;
        for (Integer i : tmp) {
            sum = sum + i;
        }
        return sum;
    }