hot100-39 组合总和

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]

思路

回溯算法+剪枝
去重（组合问题不考虑顺序（使用begin），排序问题考虑顺序（使用used））
双端队列 Deque 代替 Stack，方法一样
res.add(new ArrayList<>(path))为何要new？

首先在纸上画出搜索过程：

说明：

以 target = 7 为根结点，创建一个分支的时做减法；
每一个箭头表示：从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值；
减到 0 或者负数的时候停止，即：结点 0 和负数结点成为叶子结点；
所有从根结点到结点 0 的路径（只能从上往下，没有回路）就是题目要找的一个结果。

Q：去重

产生重复的原因是：在每一个结点，做减法，展开分支的时候，由于题目中说每一个元素可以重复使用，我们考虑了所有的候选数，因此出现了重复的列表。

可不可以在搜索的时候就去重呢？答案是可以的。遇到这一类相同元素不计算顺序的问题，我们在搜索的时候就需要按某种顺序搜索。具体的做法是：每一次搜索的时候设置下一轮搜索的起点 begin，请看下图。

A：从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。

PS：什么时候使用 used 数组，什么时候使用 begin 变量。这里为大家简单总结一下：

排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索（去重），此时使用 begin 变量。

Q：在往res中添加路经集合时为什么需要new一下，res.add(new ArrayList<>(path))可以跑通，我把他改为res.add(path)就跑不通？

A：因为 path 是对象类型（区别于基本数据类型），res.add(path) 的意思是，把 path 的「地址」添加到 res 中，path 在深度优先遍历以后为空列表，所以您最后会看到 res 中是一个一个的空列表，它们都指向一块内存。

new ArrayList<>() 的作用是复制，把遍历到叶子结点的时候 path 的样子复制出来，到一个新的列表，这样写得话，最后 res 里保存的就是不同的变量了。

这一块需要掌握的知识点是「对象类型和基本类型变量在方法传递中的不同行为」。

代码

public class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序是剪枝的前提
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(candidates, 0, len, target, path, res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
        // 由于进入更深层的时候，小于 0 的部分被剪枝，因此递归终止条件值只判断等于 0 的情况
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < len; i++) {
            // 重点理解这里剪枝，前提是候选数组已经有序，
            if (target - candidates[i] < 0) {
                break;
            }

            path.addLast(candidates[i]);
            dfs(candidates, i, len, target - candidates[i], path, res); //改变参数 begin 和 target
            path.removeLast();  //重置状态，回到递归之前的状态
        }
    }
}