leetcode刷题day23|回溯算法Part02（39. 组合总和、40.组合总和II、131.分割回文串）

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;
    }
}