给定一个数组 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]
]
class Solution {
private List<List<Integer>> list = new ArrayList<>();
private List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates.length == 0 || (candidates.length == 1 && candidates[0] != target)) {
return list;
}
Set<Integer> set = new HashSet<>();
for (int candidate : candidates) {
set.add(candidate);
}
Integer[] candidate = set.toArray(new Integer[0]);
List<Integer> myList = new ArrayList<>();
test(candidate, target, 0, myList);
return list;
}
private void test(Integer[] candidate, int target, int start, List<Integer> myList) {
if (target < 0) {
return;
}
if (target == 0) {
list.add(new ArrayList<>(myList));
}
for (int i = start; i < candidate.length; i++) {
myList.add(candidate[i]);
test(candidate, target - candidate[i], i + 1, myList);
myList.remove(myList.size() - 1);
}
}
}
-
list.toArray(new Integer[0])可以得到一个指定泛型的数组
思路是先用set去重再进行回溯求和
测试数据 combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8)
结果少了个结果[1,1,6] 自己理解错了
是只允许出现一次不是不允许重复
力扣上的做法
private void process(int start, int[] candidates, int target, List<Integer> list) {
if (target < 0) {
return;
}
if (target == 0) {
lists.add(new ArrayList<>(list));
} else {
for (int i = start; i < candidates.length; i++) {
//因为这个数和上个数相同，所以从这个数开始的所以情况，在上个数里面都考虑过了，需要跳过
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
list.add(candidates[i]);
process(i + 1, candidates, target - candidates[i], list);
list.remove(list.size() - 1);
}
}
作者：reedfan
链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/di-gui-hui-su-jiang-jie-chao-xiang-xi-by-reedfan/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
如果有重复就是在子树里循环重复,这里作者在递归之前先进行了排序Arrays.sort(candidates) 所以只要和之前的的循环进行比对,就把去重做好了
总结
回溯法 也是递归的一种应用,也走不出自己调用自己的框架
回溯的精华在于:
- 不管成功失败
(即递归结束) - 都进行回溯
(即把集合的最后一位消除) - 尝试新的可能,
(开始新的一轮循环) - 如果符合条件 加到总集合中,
(lists.add(new ArrayList<>(list));) - 如果不符合条件,结束递归
(return)
