40、组合总和 ||
题目：
此题与39、组合总和是相同的题型，都要求得出的组合不能有重复的。唯一的不同是。39题数组元素不能重复，但组合中可以重复选择数组元素；而本题数组元素有重复，且组合中不能重复选择数组元素。
题解：
如何去重：1、既然本题是数组元素中有重复项，并且最后回溯出的组合不能有重复，因此肯定要对数组进行排序，以及在判断中如若发现当前迭代项与上一个迭代项相同，则跳过此次迭代。（有点类似于15、三数之和中去重的方法，排序、判断相邻项是否相同）2、每一层回溯迭代时，起点都为上一层递归传入的数组元素之后。
剩下得出组合的方式和39题相同，使用了回溯法，回溯树根为target，每个分支target都会减掉1个数组元素，直到target==0（满足）或者小于0（不满足）。回溯树的每一层迭代时的起点都是上一层递归传入的数组元素之后，这也是避免重复的方式之一。
排序判断前后去重！每层回溯迭代时起点为上层传入点之后去重！获得组合的方法是回溯！根是target！递归减元素！直到零或负。
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
| class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates.length == 0 || target < 0) {
return result;
}
Arrays.sort(candidates);
List<Integer> list = new ArrayList<Integer>();
bfs(candidates, target, 0, list);
return result;
}
public void bfs(int[] candidates, int target, int start, List<Integer> list) {
if (target == 0) {
result.add(new ArrayList<Integer>(list));
} else if (target < 0) {
return;
}
for (int i = start; i < candidates.length; i++) {
if(i > start && candidates[i] == candidates[i - 1]) {
continue;
}
list.add(candidates[i]);
bfs(candidates, target - candidates[i], i + 1, list);
list.remove(list.size() - 1);
}
}
}
|
上一篇：6、Apache网页服务器安全架构
下一篇：39-组合总和
