景真

外观

组合总和

约 1011 字大约 3 分钟

回溯

2025-03-02

39. 组合总和

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

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

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

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

回溯，和为指定值长度无限制的元素无重可复选组合。

和为指定值长度无限制的元素无重可复选组合。base case：找到目标和或超过目标和，因为和的增长未必连续。

元素无重可复选与元素无重不可复选的区别是可复选的回溯函数每次都是从起点开始遍历，不可复选的回溯函数每次都从下一个位置开始遍历。

就一个元素可重需要注意，可重分为组合问题和排列问题，都需要排序加横向剪枝。

组合时的子递归是从下一个节点开始，排列时的子递归是从头开始，因为是从头开始，所以往往需要去重，除非题目说可以复选。

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    List<Integer> track = new LinkedList<>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates.length == 0) {
            return res;
        }
        backtrack(candidates, 0, target, 0);
        return res;
    }

    // 回溯算法主函数，sum可以是参数也可以是全局变量。
    void backtrack(int[] candidates, int start, int target, int sum) {
        if (sum == target) {
            // 找到目标和，注意这里要创建新队列，不能直接把track加到res中。
            res.add(new LinkedList<>(track));
            return;
        }
        if (sum > target) {
            // 超过目标和，直接结束。这行代码不能删，因为sum的增长不是连续的，有可能直接越过target。
            return;
        }

        // 回溯算法框架
        for (int i = start; i < candidates.length; i++) {
            // 选择 candidates[i]
            track.add(candidates[i]);
            sum += candidates[i];
            // 递归遍历下一层回溯树，注意这里是从i（注意不是起点0！）开始遍历，因为题目说元素可复选。
            backtrack(candidates, i, target, sum);
            // 撤销选择 candidates[i]
            sum -= candidates[i];
            track.removeLast();
        }
    }
}

  • 时间复杂度：O(S)O(S)，其中 SS 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和， 即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 O(n×2n)O\left(n \times 2^n\right) 是一个比较松的上界， 即在这份代码中，nn 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件， 递归的时候我们还会用 target−candidates[idx]≥0target - candidates[idx] \geq 0 进行剪枝，所以实际运行情况是远远小于这个上界的。

    上面的分析可能有错误，上界应该是O(n*n^(target / min))。res.add(new LinkedList<>(track));的时间复杂度是 O(n)。 new LinkedList<>(track)` 的时间复杂度是 `O(n)`，而 `res.add(...)` 的时间复杂度是 `O(1)`。

  • 空间复杂度：O(target)O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 OO (target) 层。