文章目录
- [39. 组合总和](https://leetcode-cn.com/problems/combination-sum/)
- [40. 组合总和 II](https://leetcode-cn.com/problems/combination-sum-ii/)
39. 组合总和
难度中等1141
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
思路分析：根据示例 1：输入: candidates = [2, 3, 6, 7]，target = 7。
候选数组里有 2，如果找到了组合总和为 7 - 2 = 5 的所有组合，再在之前加上 2 ，就是 7 的所有组合；
同理考虑 3，如果找到了组合总和为 7 - 3 = 4 的所有组合，再在之前加上 3 ，就是 7 的所有组合，依次这样找下去。
回溯,减支
package com.nie.OneJanLC;/*
*
*@auth wenzhao
*@date 2021/1/26 11:03
*/
import java.util.ArrayList;
import java.util.List;
public class LEE039 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
getRes(res, new ArrayList<>(), candidates, target, 0);
return res;
}
/**
* @param res 结果集合
* @param list 从根结点到叶子结点的路径，是一个栈
* @param candidates 候选数组
* @param target 每减去一个元素，目标值变小
* @param start 搜索起点
*/
private void getRes(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start) {
if (target == 0) {
res.add(new ArrayList<>(list));
return;
}
// 重点理解这里从 start 开始搜索的语意
for (int i = start; i < candidates.length; i++) {
// 重点理解这里剪枝，前提是候选数组已经有序， 数组中剩余的数大于要要求和的
if (target < candidates[i]) {
continue;
}
list.add(candidates[i]);
// 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
getRes(res, list, candidates, target - candidates[i], i);
// 状态重置
list.remove(list.size() - 1);
}
}
}
40. 组合总和 II
难度中等478
给定一个数组 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]
]
package com.nie.OneJanLC;/*
*
*@auth wenzhao
*@date 2021/1/26 11:03
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LEE040 {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
getRes(candidates, new ArrayList<>(), res, target, 0);
return res;
}
private void getRes(int[] candidates, ArrayList<Integer> list, List<List<Integer>> res, int target, int start) {
if (target == 0) {
res.add(new ArrayList<>(list));
return;
}
for (int i = start; i < candidates.length; i++) {
// 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
if (target < candidates[i]) {
continue;
}
// 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
list.add(candidates[i]);
// 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
getRes(candidates, list, res, target - candidates[i], i + 1);
list.remove(list.size() - 1);
}
}
}
注:解释语句: if cur > begin and candidates[cur-1] == candidates[cur] 是如何避免重复的。
这个避免重复当思想是在是太重要了。
这个方法最重要的作用是，可以让同一层级，不出现相同的元素。即
1
/ \
2 2 这种情况不会发生 但是却允许了不同层级之间的重复即：
/ \
5 5
例2
1
/
2 这种情况确是允许的
/
2
为何会有这种神奇的效果呢？
首先 cur-1 == cur 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。
可是问题来了，如果把所有当前与之前一个元素相同的都砍掉，那么例二的情况也会消失。
因为当第二个2出现的时候，他就和前一个2相同了。
那么如何保留例2呢？
那么就用cur > begin 来避免这种情况，你发现例1中的两个2是处在同一个层级上的，
例2的两个2是处在不同层级上的。
在一个for循环中，所有被遍历到的数都是属于一个层级的。我们要让一个层级中，
必须出现且只出现一个2，那么就放过第一个出现重复的2，但不放过后面出现的2。
第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin.