leetcode 40. 组合总和 II
题目：40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例1:
输入: candidates = [10,1,2,7,6,1,5], target = 8
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例2:
输入: candidates = [2,5,2,1,2], target = 5
所求解集为:
[
[1,2,2],
[5]
]
方法：Backtracking（回溯）
思路：Backtracking（回溯），通过事先对candidates排序，在回溯递归选取元素时，如果当前选取元素是同层递归的非第一选取元素且与在candidates中的前一个元素相等时，直接跳过该元素的选取。
运行数据：执行用时：4 ms，内存消耗：39.8 MB
复杂度分析：
- 时间复杂度：O(n * 2^n)，n为candidates中元素的个数，生成所有子集的时间复杂度O(2^n)，复制到输出集合中的时间复杂度O(n)。
- 空间复杂度：O(n)，n为为candidates中元素的个数，回溯递归时保存临时组合。
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
|
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
backtracking(candidates, target, result, new ArrayList<>(), 0);
return result;
}
private void backtracking(int[] candidates, int target, List<List<Integer>> result, List<Integer> combinationSumList, int t) {
if (target == 0) {
result.add(new ArrayList<>(combinationSumList));
return ;
}
for (int i = t; i < candidates.length; i++) {
if (i > t && candidates[i] == candidates[i - 1]) {
continue;
}
if (candidates[i] <= target) {
combinationSumList.add(candidates[i]);
backtracking(candidates, target - candidates[i], result, combinationSumList, i + 1);
combinationSumList.remove(combinationSumList.size() - 1);
}
}
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
