[LeetCode] 每日一题 40. 组合总和 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
解题思路
首先,我们可以想到通过回溯来进行求解。回溯的核心思想是,从当前的候选集合中挑选一个数字,然后递归地探索剩下的数字,直到达到目标值。每当目标值为零时,我们就找到了一个有效的组合
最重要的一点是去重操作。由于候选集合中可能有重复数字,为了避免产生重复的组合,我们需要对数字进行排序,然后在选择数字时跳过相同的数字,确保每次递归时选到的数字都是唯一的
具体步骤:
排序:先对候选数组进行排序,这样相同的数字会在一起,方便去重
回溯递归:每次选择当前数字或跳过相同的数字,递归探索下一个数字,直到达到目标值
去重:在回溯中,如果当前数字与前一个数字相同且前一个数字未被使用,则跳过,避免重复组合
代码实现
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)
总结
这道题考察了回溯算法的应用,同时也考察了如何处理数组中的重复元素。通过对数组排序并加以条件判断,我们可以有效地去除重复的组合。回溯算法的核心在于通过递归逐步试探,并且回溯到上一步时撤销当前选择,确保搜索空间的完整性
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。