39. 组合总和
思路:这个题与77. 组合的差异在于元素可以无限制重复被选取,那么只需要更改startIndex即可,每一层递归都可以从头选用元素。
回溯三部曲与77. 组合基本一致。
代码如下:
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backTracking(candidates,target,0);
return result;
}
public void backTracking(int[] candidates, int target, int startIndex){
if(target==0){
result.add(new ArrayList(path));
return;
}else if(target<0){
return;
}
for(int i=startIndex;i<candidates.length;i++){
path.add(candidates[i]);
backTracking(candidates,target-candidates[i],i);
path.removeLast();
}
}
}
注意:如果是一个集合来求组合的话,需要startIndex,例如:77.组合,216.组合总和III;如果是多个集合取组合,各个集合之间相互不影响,不用startIndex。我一开始没用startIndex,导致递归过程(同一树枝上)中重复扫描前面的元素,结果出现了重复的组合。
40.组合总和II
思路:这个题跟39. 组合总和的区别在于给定数组中有重复元素,但要求最终的结果集合里面不能有重复数组。把回溯理解为树的结构,元素在同一树枝上是可以重复的,但在同一层上不能重复。要实现同一层上不重复出现需要对数组排序,当当前元素与上一次遍历的元素相同时跳过。
题目要求candidates 中的每个数字在每个组合中只能使用 一次 ,所以也要使用startIndex进行约束,每次递归函数调用i要加1。
代码如下:
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backTracking(candidates,target,0);
return result;
}
public void backTracking(int[] candidates,int target,int startIndex){
if(target==0){
result.add(new ArrayList(path));
return;
}else if(target<0){
return;
}
for(int i=startIndex;i<candidates.length;i++){
if(i>startIndex && candidates[i]==candidates[i-1]) continue;
path.add(candidates[i]);
backTracking(candidates,target-candidates[i],i+1);
path.removeLast();
}
}
}
131.分割回文串
切割问题类似组合问题,例如对于字符串abcdef:
组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。
回溯三部曲:
1、递归函数参数:全局变量:数组path存放切割后回文的子串,二维数组result存放结果集。 递归函数参数:原字符串;startIndex,因为切割过的地方不能重复切割,和组合问题是一样的;新的StringBuilder字符串,存放切割后的字符子串,如果字符串是回文子串,将其加入path,递归进行下一次切割。
2、终止条件:切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止条件。切割线即startIndex的位置。
3、单层搜索的逻辑:在for (int i = startIndex; i < s.size(); i++)循环中,我们 定义了起始位置startIndex,那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是回文,如果是回文,就加入path中,path用来记录切割过的回文子串。
还有一个问题是如何判断回文子串:可以使用双指针法,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就是回文字符串了。
代码如下:
class Solution {
List<List<String>> result=new ArrayList<>();
List<String> path=new LinkedList<>();
public List<List<String>> partition(String s) {
backTracking(s,0,new StringBuilder());
return result;
}
public void backTracking(String s,int startIndex,StringBuilder sb){
if(startIndex==s.length()){
result.add(new ArrayList(path));
return;
}
for(int i=startIndex;i<s.length();i++){
sb.append(s.charAt(i));
if(check(sb)){
path.add(sb.toString());
backTracking(s,i+1,new StringBuilder());
path.removeLast();
}
}
}
public boolean check(StringBuilder sb){
for(int i=0;i<sb.length()/2;i++){
if(sb.charAt(i)!=sb.charAt(sb.length()-1-i)) return false;
}
return true;
}
}
这个题相对困难,要理解清楚怎么切割,怎么回溯,怎么存放。
标签:39,target,组合,int,startIndex,candidates,new,path,总和 From: https://blog.csdn.net/m0_51007517/article/details/142356143