算法训练营day24 | {39.组合总和, 40.组合总和II, 131.分割回文串}

第七章回溯算法part02，继续回溯法解决组合问题，思考问题之间限制条件的区别，以及考虑剪枝优化。

39. 组合总和

• 题目链接：39. 组合总和
• 文档讲解：代码随想录–39. 组合总和
• 视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！
• 状态：本题的特点是节点是同一个集合，但集合中的元素可以重复选取，but需要控制for循环遍历的起始位置。

1.1 解题分析

本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex？

• 如果是一个集合来求组合的话，就需要startIndex

• 如果是多个集合求组合，各个集合之间互不影响，那就不用startIndex。

• 分析回溯算法三部曲：

  1. 参数和返回值是什么？ 定义全局变量path、result列表；形参包括整数数组candidates、目标整数target（做减法），startIndex记录起始遍历下标
  2. 确定递归的终止条件。 当target <= 0时就要返回了，如果正好等于0，则找到了一个可行解，记录到result中；
  3. 确定单层搜索的过程。 for循环用于横向遍历，从startIndex开始遍历集合中的每个元素；递归用于纵向遍历，注意和回溯配合使用。

• 分析剪枝：在for循环的搜索范围上做文章，对总集合排序之后，如果下一层的target已经小于0，就没要进入下一层递归，结束本for循环遍历。

▶

39. 组合总和

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return results;
    }

    private void backtracking(int[] candidates, int target, int startIndex) {
        if (target <= 0) {
            if (target == 0) results.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length && target - candidates[i] >= 0; i++) {
            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i);
            path.remove(path.size() - 1);
        }
    }
}

40. 组合总和II

• 题目链接：40.组合总和II
• 文档讲解：代码随想录–40.组合总和II
• 视频讲解：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II
• 状态：难点是怎么去重呢？解集中不能包含重复的组合。

2.1 解题分析

• 本题的难点在于集合有重复元素，但还不能有重复的组合。如何去重？
• 所谓去重，其实就是使用过的元素不能重复选取。都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。对于本题，应该在同一数层上去重。
• 树层去重的话，需要对数组排序。

• 参数与上一题的区别在于：多使用了一个used数组，用来记录同一树枝上的元素是否使用过，而同一树层，used数组是回溯过去的。

• 单层搜索的逻辑，最大的不同就是要去重，要判断同一树层上相同的元素是否已经被使用过。

• 关于剪枝优化，在组合和已经超过目标target的情况下立即停止递归，而不是只在递归开始时检查target，从而减少不必要的递归调用和计算。

▶

40. 组合总和II

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);  // 排序是去重和剪枝的基础
        backtracking(candidates, target, 0);
        return results;
    }

    private void backtracking(int[] candidates, int target, int startIndex) {
        if (target <= 0) {
            if (target == 0) results.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (i > startIndex && candidates[i] == candidates[i - 1]) continue;  // 去重
            if (target < candidates[i]) return;  // 剪枝
            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            path.remove(path.size() - 1);
        }
    }
}

131. 分割回文串

• 题目链接：131. 分割回文串
• 文档讲解：代码随想录–131.分割回文串
• 视频讲解：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！
• 状态：给一套分割方案，要让每个字串都是回文串，就算是暴力枚举也很难写。

3.1 解题分析

切割问题可以抽象为组合问题，也可以抽象为一棵树形结构，难点在于切割线在代码中如何体现？–在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。

• 分析回溯算法三部曲：
  1. 参数和返回值是什么？ 定义全局变量path数组存放切割后的回文的子串，result数组存放结果集。形参还需要startIndex，已经切割过的地方不能重复切割。
  2. 确定递归的终止条件。 切割线切到了字符串末尾，说明找到了一种切割方法，本层递归终止。
  3. 确定单层搜索的过程。 判断这个子串是不是回文，放在单层递归中进行判断，for循环横向遍历时，截取子串。和回溯配合使用，纵向递归。

▶

131. 分割回文串

class Solution {
    private List<String> path;
    private List<List<String>> result;

    public List<List<String>> partition(String s) {
        path = new ArrayList<>();
        result = new ArrayList<>();
        backtracking(s, 0);
        return result;
    }

    private void backtracking(String s, int startIndex) {
        if(startIndex == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            String sub = s.substring(startIndex, i + 1);
            if (!isHuiWen(sub)) continue;
            path.add(sub);
            backtracking(s, i + 1);
            path.remove(path.size() - 1);
        }
    }
    
    private boolean isHuiWen(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}