文章

[LeetCode] 每日一题 40. 组合总和 II

题目链接

https://leetcode.cn/problems/combination-sum-ii

题目描述

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

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

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

示例输入

示例 1

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

示例 2

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

提示

  • 1 <= candidates.length <= 100

  • 1 <= candidates[i] <= 50

  • 1 <= target <= 30

解题思路

首先,我们可以想到通过回溯来进行求解。回溯的核心思想是,从当前的候选集合中挑选一个数字,然后递归地探索剩下的数字,直到达到目标值。每当目标值为零时,我们就找到了一个有效的组合

最重要的一点是去重操作。由于候选集合中可能有重复数字,为了避免产生重复的组合,我们需要对数字进行排序,然后在选择数字时跳过相同的数字,确保每次递归时选到的数字都是唯一的

具体步骤:

  1. 排序:先对候选数组进行排序,这样相同的数字会在一起,方便去重

  2. 回溯递归:每次选择当前数字或跳过相同的数字,递归探索下一个数字,直到达到目标值

  3. 去重:在回溯中,如果当前数字与前一个数字相同且前一个数字未被使用,则跳过,避免重复组合

代码实现

class Solution {
    List<Integer> temp = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        used = new boolean[candidates.length];
        backtrace(candidates, target, 0);
        return res;
    }

    private void backtrace(int[] candidates, int target, int startIndex) {
        if (target == 0 && !temp.isEmpty()) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) {
                return;
            }
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            temp.add(candidates[i]);
            backtrace(candidates, target - candidates[i], i + 1);
            temp.remove(temp.size() - 1);
            used[i] = false;
        }
    }
}

复杂度分析

  • 时间复杂度

    • 由于我们在回溯过程中每次都选择一个数字来递归,最坏情况下会遍历所有的组合。对于一个有 n 个元素的数组,回溯树的深度为 n,且每层最多有 n 个分支。因此,最坏情况下的时间复杂度是 O(2^n),即遍历所有可能的组合

    • 对于去重操作,我们通过排序和标记已使用的元素来避免重复,因此排序的时间复杂度为 O(n log n)

  • 空间复杂度

    • 回溯算法需要使用递归栈空间,最深的递归层数为 n,因此递归栈的空间复杂度为 O(n)

    • 另外,存储结果的空间需要 O(k)(其中 k 是结果中组合的数量)。因此,总空间复杂度为 O(k + n)

总结

这道题考察了回溯算法的应用,同时也考察了如何处理数组中的重复元素。通过对数组排序并加以条件判断,我们可以有效地去除重复的组合。回溯算法的核心在于通过递归逐步试探,并且回溯到上一步时撤销当前选择,确保搜索空间的完整性

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0