216. 组合总和 III

题目：https://leetcode-cn.com/problems/combination-sum-iii/

代码：

class Solution {

    public List<List<Integer>> combinationSum3(int k, int n) {
        return this.handle(k, n, n);
    }

    private List<List<Integer>> handle(int k, int n, int max) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n <= 0) {
            return res;
        }
        max = max > 9 ? 9 : max;
        if (k == 1) {
            //只剩1个数，直接从1-9取符合条件的返回，为了去重，max的值也要考虑
            if (n <= max) {
                List<Integer> list = new ArrayList<>();
                list.add(n);
                res.add(list);
            }
        }else{
            //多个数，需要递归
            for (int i = max; i > 0; i--) {
                List<List<Integer>> lists = this.handle(k - 1, n - i, i-1);
                for (List<Integer> list : lists) {
                    list.add(i);
                }
                res.addAll(lists);
            }
        }

        return res;
    }

}

使用递归，k的值就是递归的次数，组合每一次都从1-9中最大的那个数开始遍历，考虑到数字只能使用一次，且组合不能重复，所以增加了一个max的字段，组合每一次遍历变为从1-min(9,max)中最大的那个数开始遍历。