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)中最大的那个数开始遍历。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

维特丝(vetes)泡沫发蜡喷雾干胶定型弹力素羊毛卷男女保湿蓬松发胶 泡沫发蜡450ml+旅行装99ml
¥34.00
维特丝(vetes)一梳黑染发剂染发梳植物潮色显白遮盖白发自然清水纯黑发焗油男女梳炫彩 自然黑LW00
¥49.00
维特丝(vetes)染发笔遮白补染快速染发天然植物一次性染发棒 一次性染发棒黑色
¥46.00
维特丝 护发精油防毛躁清香玫瑰奇焕亮发干枯烫发卷发直发头发润发护发素男女士 滋养柔顺护发精油100ml
¥36.00