39 组合总和

一、题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

二、题解

思路：回溯 / DFS / 剪枝

1. 核心思路

这道题要求找出所有和为 target 的组合，并且每个数字可以重复使用，因此可以使用 回溯法。

回溯的核心是：

  • 每次从 candidates 中选择一个数字加入当前组合；
  • 如果当前组合的和等于 target，说明找到一个答案；
  • 如果当前组合的和大于 target，说明当前路径不合法，需要返回；
  • 为了避免重复组合，需要用 start 控制每一层从哪里开始搜索。

例如：

candidates = [2,3,6,7]
target = 7

组合 [2,2,3] 是合法的。

但是 [2,3,2] 和 [3,2,2] 本质上和 [2,2,3] 是同一种组合，只是顺序不同，所以不能重复记录。

因此每次递归时，只能从当前下标及其后面的位置继续选。

2. 具体步骤

  1. 先对 candidates 排序，方便后续剪枝。
  2. 定义结果集 result，用于保存所有合法组合。
  3. 定义路径 path，用于保存当前正在尝试的组合。
  4. 从下标 start 开始遍历候选数组。
  5. 每次选择一个数字加入 path。
  6. 因为数字可以重复使用，所以递归时仍然从当前下标 i 开始。
  7. 如果当前和等于 target，把当前路径加入结果集。
  8. 如果当前和大于 target，直接返回。
  9. 回溯时撤销上一次选择，继续尝试其他数字。

3. 关键逻辑

关键点一：为什么递归时传 i，不是 i + 1？

backtrack(candidates, target, i, sum + candidates[i]);

因为题目说同一个数字可以重复使用。

例如要得到：

[2,2,3]

第一次选了 2 之后，下一层还可以继续选 2。

所以递归时传入的是 i。

如果传入 i + 1，就表示当前数字不能再次使用了。

关键点二：为什么需要 start？

start 用来避免重复组合。

例如：

[2,3,2]
[3,2,2]

这两个组合和 [2,2,3] 本质上是一样的，只是顺序不同。

所以我们规定后面选择的数字不能回头选前面的数字，这样就可以避免重复。

关键点三：为什么排序后可以剪枝？

因为数组已经排好序，如果：

sum + candidates[i] > target

说明当前数字加入后已经超过 target。

由于后面的数字只会更大，所以后面的数字也不用继续尝试了，可以直接 break。

三、代码

import java.util.*;

class Solution {
    // 保存最终结果
    private List<List<Integer>> result = new ArrayList<>();

    // 保存当前路径
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 1. 排序，方便剪枝
        Arrays.sort(candidates);

        // 2. 从下标 0 开始回溯，当前和为 0
        backtrack(candidates, target, 0, 0);

        // 3. 返回结果
        return result;
    }

    /**
     * @param candidates 候选数组
     * @param target     目标和
     * @param start      本层搜索的起始位置
     * @param sum        当前路径的数字和
     */
    private void backtrack(int[] candidates, int target, int start, int sum) {
        // 当前和等于 target，说明找到一个合法组合
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 当前和大于 target，说明这条路径不合法
        if (sum > target) {
            return;
        }

        // 从 start 开始，避免出现重复组合
        for (int i = start; i < candidates.length; i++) {
            // 剪枝：如果当前数字加入后已经超过 target，后面更大的数字也不用尝试
            if (sum + candidates[i] > target) {
                break;
            }

            // 选择当前数字
            path.add(candidates[i]);

            // 因为同一个数字可以重复使用，所以这里传 i，不是 i + 1
            backtrack(candidates, target, i, sum + candidates[i]);

            // 撤销选择，尝试其他数字
            path.remove(path.size() - 1);
        }
    }
}

四、复杂度分析

时间复杂度：O(ntarget/min)O(n^{target / min})

说明：

其中 n 是 candidates 的长度，min 是数组中的最小值。

因为每一层最多有 n 种选择，递归深度最多为 target / min，所以时间复杂度可以粗略表示为：

O(n^(target / min))

回溯问题的时间复杂度通常和搜索树规模有关，实际运行中会因为剪枝减少很多搜索。

空间复杂度：O(target/min)O(target / min)

说明：

递归深度最多为 target / min，当前路径 path 的最大长度也最多为 target / min。

如果把最终返回结果也算入空间复杂度，则还需要额外计算结果集占用的空间。

评论