DFS与回溯专题：组合总和III

    DFS与回溯专题：组合总和III

题目链接: 216.组合总和III

参考题解: 代码随想录

题目描述

代码纯享版

class Solution {

    List<List<Integer>> list_all = new ArrayList();
    List<Integer> list = new ArrayList();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k, n, 1);
        return list_all;
    }

    void backtrack(int k, int n, int start){

        if(list.size() == k){
            int sum = 0;
            for(int i = 0; i < list.size(); i++){
                sum += list.get(i);
            }
            if(sum == n) {
                list_all.add(new ArrayList(list));
            }
            return;
        }

        for(int i = start; i <= 9 - (k - list.size()) + 1; i++){
            list.add(i);
            backtrack(k, n, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

代码逐行解析版

class Solution {

    List<List<Integer>> list_all = new ArrayList();
    List<Integer> list = new ArrayList();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k, n, 1); //回溯
        return list_all;
    }

    void backtrack(int k, int n, int start){

        if(list.size() == k){ //list列表为k个数时
            int sum = 0; //创建sum来统计相加之和
            for(int i = 0; i < list.size(); i++){ //将列表所有的数相加
                sum += list.get(i);
            }
            if(sum == n) { //如果sum和n相等
                list_all.add(new ArrayList(list)); //添加到结果链表
            }
            return; //返回
        }

        for(int i = start; i <= 9 - (k - list.size()) + 1; i++){
            list.add(i); //将i添加到列表
            backtrack(k, n, i + 1); //回溯
            list.remove(list.size() - 1); //列表删掉最后一个元素
        }
    }
}