回溯遍历可能选项，二分法加快效率，39题的变式
给定一个数组 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]
]
思路：
此题完全可以沿用上一题的模板。
我们先对数组排序，之后二分地找到最大的小于等于 target 的数，从这个数开始向下回溯递归地进行 DFS搜索。
只需注意，上题的每个元素是无限量的，而本题中的元素有限。为了不漏掉重复的元素，同时不重复考虑重复的元素，我们只需在每次递归当中，在循环每次要进入下层递归前，判断当前循环考虑的元素是否与前一次循环重复，重复则略过即可。
时间复杂度：O(2^n * n) 其中 2^n 是指元素个数为 n 的集合所对应的幂集中的元素数量。
空间复杂度：O(n)
实现：
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
41
42
43
44
45
46
47
| class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
nums = candidates;
ret = new LinkedList<>();
toAppend = new LinkedList<>();
DFS(target, candidates.length - 1);
return ret;
}
private int[] nums;
private List<List<Integer>> ret;
private LinkedList<Integer> toAppend;
private void DFS(int target, int right) {
int l = 0, r = right;
while (l <= r) {
int mid = l + ((r - l) >> 1);
int val = nums[mid];
if (target < val) {
r = mid - 1;
} else {
l = mid + 1;
}
}
int ptr = l - 1;
if (ptr < 0) {
return;
}
int prevVal = -1;
for (; ptr >= 0; ptr--) {
int val = nums[ptr];
if (val == prevVal) {
continue;
}
toAppend.addLast(val);
int deeperTarget = target - val;
if (deeperTarget == 0) {
ret.add(new LinkedList<Integer>(toAppend));
} else {
DFS(deeperTarget, ptr - 1);
}
toAppend.removeLast();
prevVal = val;
}
}
}
|
