0039.md

39. 组合总和

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

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

说明：

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

示例 1：

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

示例 2：

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

分析阶段

在一个没有重复元素的数组中，找到所有和值等于 target 的组合，且要求组合不能重复。

1、问题类型

第二类：对某种数结构和算法的使用

使用的算法：在给定的元素集合中，找到满足条件的组合，使用“回溯算法“

数据结构：回溯算法需要构建空间状态树，使用树结构

2、解题思路

“回溯算法”要确定以下条件，然后构建出解集的空间状态树。

（1）选择列表

给定的数组就是选择列表。

（2）路径

• 记录已经选择的元素值，以及当前路径中所有元素的和值；

• 记录已经选择的路径，避免组合重复。

（3）结束条件

达到什么条件时结束结束当前节点的遍历？

• 路径中所有元素值和大于 target，当前路径无效，结束遍历；

• 路径中所有元素值和等于 target，把路径添加到结果集中，结束遍历；

• 路径已经在结果集中。

（4）选择

什么条件下才把当前元素添加进路径中？

• 当前元素与路径中元素的和值小于 target 时，才把当前元素添加到路径中

根据上述条件构建“空间状态树”，下图中 $candidates = [2,3,6,7],target = 7$：

从图中可以看出：

1、在根节点时，选择的路径中没有元素

2、选择第一层左子节点，选择“2“，路径中有1个元素”2“

3、选择第二层左子节点，选择“2“，路径中有2个元素”2“，依次类推

4、直到某一层，路径中所有元素和等于8，大于 target，是无效路径，回退到上一个节点，再选择元素“3”，路径中和值等于 target，是有效路径

5、因为每个元素是可以重复使用的，所以在每层选择时，要包含数组中的所有元素

编码阶段

基础版本

class Solution {
    public static void main(String[] args) {
        int[] candidates = new int[]{2, 3, 6, 7};
        int target = 7;
        System.out.println("=======" + new Solution().combinationSum(candidates, target));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> path = new ArrayList<>();
		// 保存有效路径，用于判重
        Set<String> subSet = new HashSet<>();

        backtrack(res, path, subSet, candidates, 0, target);
        return res;

    }

    public void backtrack(List<List<Integer>> res, List<Integer> path, Set<String> subSet, int[] candidates, int sum, int target) {
        if (sum == target) {
            // 把有效路径排序后，转换成字符串，在集合中判断是否重复
            String key = path.stream().sorted().map(Object::toString).collect(Collectors.joining(""));
            if (!subSet.contains(key)) {
                subSet.add(key);
                res.add(new ArrayList<>(path));
            }
            return;
        }

        for (int candidate : candidates) {
            if (candidate + sum > target) {
                continue;
            }

            path.add(candidate);
            backtrack(res, path, subSet, candidates, sum + candidate, target);

            path.remove(path.size() - 1);
        }
    }
}

优化版本1

上面代码存在以下问题：

• 每次递归都是从数组的第一个元素开始遍历，做了重复操作；因为某一层递归中，遍历完第$i$个元素的所有可能路径之后，在遍历第$i+1$个元素时，如果再从数组下标0重新开始遍历，只会生成重复路径；因为要求不能有重复的组合，所以上面的代码使用了一个字符串集合对路径进行去重，导致每次把路径添加进结果集时，都要做一次排序；
• 变量 sum 是多余的，可以另一变量 diff 来记录路径中和值与 target 之间的差值。

优化如下：

• 为了避免有重复路径，在每次遍历时，不需要从数组的下标0开始，可以从当前元素的位置开始；
• 使用一个 diff 来记录路径中和值与 target 之间的差值，当 diff 小于0时表示路径无效，当diff等于0时表示路径有效。

代码如下：

class Solution {
    public static void main(String[] args) {
        int[] candidates = new int[]{2, 3, 6, 7};
        int target = 7;
        System.out.println("=======" + new Solution().combinationSum(candidates, target));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> path = new ArrayList<>();

        backtrack(res, path, candidates, target, 0);
        return res;

    }

    /**
     * 回溯递归
     *
     * @param res        结果集
     * @param path       路径
     * @param candidates 选择列表
     * @param diff       与目标值的差值
     * @param idx        当前遍历的元素下标
     */
    public void backtrack(List<List<Integer>> res, List<Integer> path, int[] candidates, int diff, int idx) {
        if (diff == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (diff < 0) {
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            if (diff - candidates[i] < 0) {
                // 跳过当前元素值
                continue;
            }

            path.add(candidates[i]);
            backtrack(res, path, candidates, diff - candidates[i], i);

            path.remove(path.size() - 1);
        }
    }
}

优化版本2

从前面代码可知，如果 diff - candidates[i] < 0 会跳过 candidates[i]；以此类推，也应该跳过大于 candidates[i] 的所有元素，这样可以减少递归的层次。

当 diff - candidates[i] < 0时，怎么才能保证后续的元素值大于 candidates[i]？

对数组进行排序，当 diff - candidates[i] < 0时，结束对数组的遍历，减少递归层次。

代码如下：

class Solution {
    public static void main(String[] args) {
        int[] candidates = new int[]{2, 3, 6, 7};
        int target = 7;
        System.out.println("=======" + new Solution().combinationSum(candidates, target));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 排序
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();

        List<Integer> path = new ArrayList<>();

        backtrack(res, path, candidates, target, 0);
        return res;

    }

    /**
     * 回溯递归
     *
     * @param res        结果集
     * @param path       路径
     * @param candidates 选择列表
     * @param diff       与目标值的差值
     * @param idx        当前遍历的元素下标
     */
    public void backtrack(List<List<Integer>> res, List<Integer> path, int[] candidates, int diff, int idx) {
        if (diff == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (diff < 0) {
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            if (diff - candidates[i] < 0) {
                // 结束遍历
                break;
            }

            path.add(candidates[i]);
            backtrack(res, path, candidates, diff - candidates[i], i);

            path.remove(path.size() - 1);
        }
    }
}

版本2与版本1最大的不同有两处：

• 先对数组进行了排序
• 提前结束遍历，减少递归层次

总结阶段

用回溯算法寻找和值等于 target 时，要根据数组中元素的特点进行优化，特别是可以先把数组排序，在一个有序数组中，如果当前元素的和值已经大于 target，就可以舍去后续的元素，有效减少递归层次。