题目

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

实现代码

使用DFS实现回溯算法 + 排序 + 剪枝

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    List<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        // 排序，为了方便去重和剪枝
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, 0);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, int sum) {

        // 找到目标组合
        if (sum == target) {
            result.add(new LinkedList<>(path));
            return;
        }
        // 剪枝：如果当前和已超过目标值，直接返回
        if (sum > target) {
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            // 去重：跳过同层的重复元素
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            // 剪枝：如果当前元素加上已有和超过目标值，后续更大的元素也不用考虑
            if (sum + candidates[i] > target) {
                break;
            }

            path.addLast(candidates[i]);
            backtrack(candidates, target, i + 1, sum + candidates[i]);
            path.removeLast();
        }
    }
}

核心思路

这道题的关键在于去重，因为数组中可能包含重复元素，但最终结果不能有重复的组合。

解决方案：

  1. 排序：将相同的元素聚集在一起，便于去重处理
  2. 去重逻辑：if (i > start && candidates[i] == candidates[i - 1]) continue;
    • 在同一层递归中，跳过重复的元素
    • 但在不同层递归中，允许使用重复元素
  3. 剪枝优化：
    • 当前和超过target时直接返回
    • 当前元素加上已有和超过target时，后续更大元素也不用考虑（因为已排序）

时间复杂度

在最坏情况下，需要遍历所有可能的组合。假设candidates大小为n：

  1. 状态空间：理论上最多有2^n种子集组合

  2. 实际剪枝效果：

    • 排序后的剪枝：当sum + candidates[i] > target时直接break，避免后续更大元素的尝试
    • target限制：只有和等于target的组合才会被加入结果
    • 去重逻辑：跳过同层重复元素，减少无用搜索

  3. 每个有效状态的处理时间：复制当前路径到结果集，时间复杂度为O(k)，其中k为当前路径长度

因此，总的时间复杂度为O(k × 2^n)，其中k为平均路径长度。但由于剪枝优化，实际运行时间会显著优于这个上界。

空间复杂度

主要的额外空间消耗来自：

  1. result：存储所有符合条件的组合。由于target限制，有效组合数量远少于2^n，具体数量取决于输入数据
  2. path：递归过程中存储当前路径，最大深度为n（最坏情况下所有元素都选中），空间复杂度为O(n)
  3. 递归调用栈：最大深度为n，空间复杂度为O(n)

因此，如果不计算输出结果的存储空间，额外空间复杂度为O(n)。包含输出结果时，空间复杂度取决于有效组合的数量和平均长度。