[数据结构与算法]LeetCode216. 组合总和 III

思路

根据回溯的模板就很容易想到了。

代码

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    int sum =0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        fun(k,n,1);
        return res;
    }
    public void fun(int k, int n,int index){
        if(sum > n){
            return;
        }
        if(path.size() == k){
            if(sum == n){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for(int i = index;i<=9;i++){
            sum +=i;
            path.add(i);
            fun(k,n,i+1);
            sum -=i;
            path.remove(path.size()-1);
        }
    }

}

2022深度学习开发者峰会

5月20日13:00让我们相聚云端，共襄盛会！