代码随想录算法训练营day27 || 39. 组合总和，40.组合总和II，131.分割回文串

视频讲解：

带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili

回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II_哔哩哔哩_bilibili

带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！_哔哩哔哩_bilibili

39. 组合总和

思路：题目中给出这样一句话：“candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的”。本质上这道题还是一道组合题，因此如何abb与bba其实重复的，并且集合中不存在重复的元素，因此为了避免颠倒的组合结果被重复的输出，需要在每一次遍历时仅保持向右的遍历方向即可。

// 时间复杂度O(n^k)，n是candidates的长度，k是ans的长度
// 空间复杂度O(kn)，应当等于结果集的大小，是所有集合所拼接在一起的大小

class Solution {
    
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length == 0)
            return ans;
        // Arrays.sort(candidates);
        backtracking(candidates, target, 0, 0);
        return ans;
    }
    public void backtracking(int[] candidates, int target, int sum, int index){
        // 终止条件
        if(sum >= target){
            if(sum == target)
                ans.add(new ArrayList<>(list));
            return;
        }

        // 既然元素可以无限次的重复取得，那么每一轮的递归都是完全的遍历整个数组
        for(int i=index; i<candidates.length; i++){
            // 节点处理，在二叉树中回溯没有for循环，而是直接将此时的循环体作为递归体
            sum+=candidates[i];
            list.add(candidates[i]);
            backtracking(candidates, target, sum, i);
            // 回溯操作
            list.remove(list.size()-1);
            sum-=candidates[i];
        }
        return;
    }
}

 40.组合总和II

思路：不同于以往的组合类型的题目，该题所给出的数据中出现了重复元素，因此在存在着重复元素的集合中输出所有的满足要求的组合，需要对组合进行去重。去重的思想就是对于重复的元素只要存在一个与其他的数据进行组合即可，而特殊的情况就是某个结果中包含有多个不同位置的重复元素，需要多次重复取他们形成一个组合。所以去重就是保留重复元素的首个元素进行递归，后续的相同元素在首个元素的树型结构已经生成完毕后就直接跳过。而为了能够使得相同的元素可以被访问到，应先对数据进行排序。

// 时间复杂度O(n^k)，n是candidates的长度，k是ans的长度
// 空间复杂度O(kn)，应当等于结果集的大小

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates.length == 0)
            return ans;
        // 这一项操作就是防止1,2,5和2,1,5这样的结果出现，当元素已经有序，那么大的数就无法再回头取小的数，只可以由小的数作为起始的时候去访问大的数
        Arrays.sort(candidates);
        boolean[] visited = new boolean[candidates.length];    
        backtracking(candidates, target, 0, -1, visited);
        return ans;
    }

    public void backtracking(int[] candidates, int target, int sum, int index, boolean[] visited){
        if(sum >= target){
            if(sum == target)
                ans.add(new ArrayList<Integer>(list));   
            return;
        }

        for(int i=index+1; i<candidates.length; i++){
            // 重复元素中的首个出现可以开展递归，其他的重复元素都要通过visited进行过滤
            // if(i-1>=0 && candidates[i] == candidates[i-1] && visited[i-1] == false)
            //     continue;
            if(i-1>=0 && candidates[i] == candidates[i-1] && i>(index+1))
                continue;
            sum += candidates[i];
            visited[i] = true;
            list.add(candidates[i]);
            backtracking(candidates, target, sum, i, visited);
            list.remove(list.size()-1);
            visited[i] = false;
            sum -= candidates[i];
        }

        return;
    }
}

131.分割回文串

思路：本题大问题是需要将一个字符串进行分割，形成多个子的回文字符串；因此所划分出的小问题就是每一次划分的位置，至少都需要保障分割位置的左边是回文字符串；带着这个思想我们进行递归函数的编写，这个思想直接指明的是回溯的循环部分怎么写，遍历的内容应该是子串的长度，如此我们就可以对每个子串进行控制，并且可以精确的确定每个划分的位置；既然循环遍历的是每个子串的长度，那么遍历结束的标志，即遍历完整个字符串就是截止条件，否则递归无法终结，也相应的推导出了所需要的截止条件，完成递归回溯的整体函数。

// 时间复杂度O(n^k)，k是ans的size
// 空间复杂度O(kn)，一共列表中将会有kn长度的字符进行存储
// 以上为自己的暂时推导，如果有错还望大家指正，非常感谢

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> list = new ArrayList<>();
    public List<List<String>> partition(String s) {
        // 仍然是组合问题
        if(s==null || s.equals(""))
            return ans;
        backtracking(s, 0);
        return ans;
    }
    public void backtracking(String s, int begin){
        // 终止条件
        if(begin == s.length()){
            ans.add(new ArrayList<String>(list));
            return;
        }
        
        // i表示的是子串的长度
        for(int i=1; begin+i<=s.length(); i++){
            int end = begin + i;
            String str = s.substring(begin, end);
            StringBuilder compare = new StringBuilder(str).reverse();
            if(compare.toString().equals(str) == true){
                list.add(str);
                backtracking(s, end);
                list.remove(list.size()-1);
            }
        }

        return;
    }
}