【LeetCode-中等题】39. 组合总和

题目

这题的nums数组里面不存在重复元素，所以也就无需做去重操作
但同一个元素可以被无限次取，说明每次递归中的for循环的开始位置就是自己

nums数组里面存在重复元素，去重版本：

方法一：递归+回溯

参考讲解视频：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！

    List<List<Integer>> res = new ArrayList<>();//最终结果集
    int len = 0;//数组长度
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);//对数组排序  方便后面做剪枝
        len = candidates.length;
        List<Integer> zres = new ArrayList<>();//子结果集
        int sum = 0;  //初始为0
        int startIndex = 0; //设置标志位  使得每次只能取自己和自己之后的数组成子结果 避免重复子集
        dfsback(candidates,zres,sum,target,startIndex);
        return res;
    }
    public void dfsback(int[]candidates, List<Integer> zres,int sum,int target,int startIndex){
        if(sum == target){
            res.add(new ArrayList<>(zres));//如果sum == target 收获节点的子集合  再往下遍历肯定大于target  所以直接return
            return;
        }
        if(sum > target) return; //如果sum大于target  后面就无需遍历了
        for(int i = startIndex ; i <len ;i++){//题目说同一个 数字可以 无限制重复被选取 那每次遍历都可以从他自己startIndex开始取到数组尾吧（一般都是i+1后面取）
            sum += candidates[i];
            zres.add(candidates[i]);
            dfsback(candidates,zres,sum,target,i);//往下递归   这里的i是为了  往下面递归不能取数组前面 的数，不然会出现重复子集  [2,2,3],[2,3,2],[3,2,2]
            sum -= candidates[i];//回溯复原原值
            zres.remove(zres.size()-1);
        }
       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25