DFS和回溯专题：组合总和

题目链接: 39.组合总和

参考题解：代码随想录

题目描述

代码纯享版

class Solution {
    
    public List<List<Integer>> list_all = new ArrayList();
    public List<Integer> list = new ArrayList();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0, 0);
        return list_all;
    }

    void backtrack(int[] candidates, int target, int start, int sum){
        
        if(sum == target){
            list_all.add(new ArrayList(list));
            return;
        }

        if(sum > target){
            return;
        }

        for(int i = start; i < candidates.length; i++){
            list.add(candidates[i]);
            backtrack(candidates, target, i, sum + candidates[i]);
            list.remove(list.size() - 1);
        }
    }
}

代码逐行解析版

class Solution {
    
    public List<List<Integer>> list_all = new ArrayList();
    public List<Integer> list = new ArrayList();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, target, 0, 0); //回溯
        return list_all;
    }

    void backtrack(int[] candidates, int target, int start, int sum){
        
        if(sum == target){ //如果数字和等于sum
            list_all.add(new ArrayList(list)); //将list添加到list_all
            return;
        }

        if(sum > target){ //如果数字和大于sum，直接返回
            return;
        }

        for(int i = start; i < candidates.length; i++){ //循环遍历整个数组
            list.add(candidates[i]); //将数组的元素添加到list
            //回溯
            //注意1:可重复，start用i；假如不能重复用同一元素，就用i+1
            //注意2:sum要加上candidates[i]
            backtrack(candidates, target, i, sum + candidates[i]); 
            list.remove(list.size() - 1); //删掉列表最后一个元素
        }
    }
}