达叔
回溯算法模版
首先上一套回溯算法模版，很多回溯算法都可以使用该模版解决
public List<List<Integer>> problem(参数不定) {
List<List<Integer>> res = new ArrayList<>();
help(参数不定);
return res;
}
public void help(参数不定){
if(满足条件){
加入解集中
return
}
for(可以选择的数据集合){
// 做选择
list.add(i)；
help()；
// 回溯
list.remove(list.size()-1);
}
}
leetcode 39 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。解集不能包含重复的组合
两个要点已经被黑体标注，数字可重复选取比较容易理解，即假设第一次选择完2之后，还可以继续选择2；对于不包含重复组合规定，我们先来看下怎么样的组合算重复，假设target = 5，candidates为2，3，那么【2，3】为一组，【3，2】同样为一组，但【3，2】算作与【2，3】重复，因为组合问题不关心解集中元素顺序，即如果两个解集中元素相同，但顺序不同，那么这两个解就算重复。
接下来看下代码，套模版
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 这里的排序非必须
help(res, candidates, target, new ArrayList(), 0);
return res;
}
private void help(List<List<Integer>> res, int[] candidates, int target, ArrayList arrayList, int index){
// 对于不满足条件的直接return，俗称剪枝
if(target < 0) {
return;
}
// 满足条件
if(target == 0) {
res.add(new ArrayList(arrayList));
rerurn;
}
// 从待选择列表中选择，注意这里index的作用在于不能让你再选择之前已经选过的集合元素了
// 比较难理解，举个例子，假设candidates为 2，3，4
// index=0，选择2，那么剩余可选为3，4
// index = 1，选择3，剩余可选为4
// index = 2，选择4，剩余可选为空
// 为什么要只让他选择index后面的元素呢？这是为了排重，假设2，3，4是一个解集，当选择4时，如果让他可以随意选取，那么就会选择到4，2，3；4，3，2的情况，所以这里限制只能选择上一轮没有选择的元素
for(int i=index;i<candidates.length;i++){
int num = candidates[I];
arrayList.add(num);
// help函数最后一个参数传i，代表着下一次循环还可以继续选择该元素
help(res, candidates, target - num, arrayList, i);
arrayList.remove(arrayList.size()-1);
}
}
代码还有可以优化的一些地方，比如剪枝代码可以拿到for循环中提前判断，存储解集的集合可以使用双端队列减少代码复杂度
leetcode 40 组合总和2
总体描述与上一题相同，只有约束条件有改变，**candidates 中的每个数字在每个组合中只能使用一次，并且candidates可能包含重复数字
同样，套模版
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
// 这里的排序是必须的
Arrays.sort(candidates);
help(res, candidates, target, new ArrayList(), 0);
return res;
}
public void help(List<List<Integer>> res, int[] candidates, int target, List<Integer> list, int index){
if(target <0){
return;
}
if(target == 0) {
res.add(new ArrayList<>(list));
return;
}
for(int i =index;i<candidates.length;i++){
if(i>index && candidates[i]==candidates[i-1]){
continue;
}
int num = candidates[I];
list.add(num);
// 每个数字只能使用一次，所以是i+1
help(res,candidates,target - num, list, i+1);
list.remove(list.size()-1);
}
}
leetcode 216 组合总和3
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
解集不能包含重复的组合
和组合2问题基本相同，唯一的区别在于加了限制解集只能包含k个数
直接套模版
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
help(res, new ArrayList(), k, n, 1);
return res;
}
public void help(List<List<Integer>> res, List<Integer> list, int k, int n, int index){
// 这里满足解集需要两个条件
if(n==0 && list.size()==k) {
res.add(new ArrayList(list));
return;
}
// 剪枝的情形也多了一个
if(n <0 || list.size() >k){
return;
}
for(int i=index; i<10; i++){
list.add(i);
help(res, list, k, n-i, i+1);
list.remove(list.size()-1);
}
}
