40. 组合总和 II

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

一、问题描述

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

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

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

二、解题思路

• 排序：
  对 candidates 数组进行排序，便于后续剪枝以及避免重复组合的产生。

• 回溯： 我们使用递归来探索所有可能的组合。在每次递归时，选择当前数字，并将目标 target 减去当前数字。如果目标 target 减为 0，说明找到了一组解，将其加入结果列表；否则继续递归寻找下一个数字。

  在每一层递归中，为了保证每个数字只使用一次，我们通过维护一个start索引，确保在递归中不会重复选择已经选过的数字。同时，为了防止相同组合出现，我们在递归过程中要跳过重复的数字。

• 剪枝： 如果当前数字大于目标 target，则无需继续递归，因为数组是排序的，后续数字只会更大。

• 终止条件：

  • 当 target == 0 时，表示找到了一组符合条件的组合，加入结果集。
  • 当 target < 0 时，停止递归。

三、代码

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // 排序，便于剪枝和去重
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    // 回溯函数
    private void backtrack(int[] candidates, int target, int start, List<Integer> combination, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(combination)); // 找到符合条件的组合
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) { // 跳过重复元素
                continue;
            }
            if (candidates[i] > target) { // 剪枝，如果当前数大于目标值，直接跳过
                break;
            }
            combination.add(candidates[i]); // 选择当前元素
            backtrack(candidates, target - candidates[i], i + 1, combination, result); // 递归
            combination.remove(combination.size() - 1); // 回溯，移除最后一个元素
        }
    }
}

四、复杂度分析

• 时间复杂度：

  • 由于题目要求找到所有符合条件的组合，时间复杂度与组合数量相关。在最坏的情况下，组合数量可能为 O(2^n)，其中 n 是 candidates 的长度，具体的时间复杂度取决于 candidates 和 target 的值。

• 空间复杂度：

  • 递归深度取决于 target 和数组的元素，因此最坏情况下递归深度为 O(n)，再加上存储结果的空间，最终空间复杂度为 O(n + k)，其中 k 是结果集的组合数量。