LeetCode算法题解（回溯）|39. 组合总和、40. 组合总和 II、131. 分割回文串

一、39. 组合总和

题目链接：39. 组合总和

题目描述：

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

算法分析：

利用经典的回溯算法。

首先创建一个二维数组用来存放所有组合的结果集，以及一个用来遍历每种合理组合的一维数组。

然后调用递归，纵向遍历组合，

传递参数：无重复数组，遍历数组的起始下标。

递归结束条件：当组合中的总和等于目标值时，将组合放入结果集，然后返回，如果组合中的总和大于目标值，则直接返回结束递归。

从起始下标横向遍历无重复数组，candidates[i]插入组合，总和sum加上candidates[i]的值，然后递归判断该组合是否满足，最后再回溯，将candidates[i]从组合中拿出来，sum减去candidates[i]的值，然后进行下一层for循环。

代码如下：

class Solution {
    List>result = new ArrayList<>();//用来存放所有组合的结果集
    LinkedList path = new LinkedList<>();//用来遍历每种组合的一维数组
    int T;//将目标整数定义在全局区域
    int sum;//记录组合总和
    int len;//记录数组candidates的长度
    public void backTravel(int[] candidates, int startIndex) {  
        if(sum == T) {//如果组合总和等于目标值，将改组和放入结果集，然后返回
            result.add(new LinkedList(path));
            return;
        }else if(sum > T) return;//由于数组中每个元素（2 <= candidates[i] <= 40）,所以当总和大于目标值时，后面无论加多少个元素，总和一定大于target,所以之间返回。
        for(int i = startIndex; i < len; i++) {//从起始下标遍横向历数组
            path.add(candidates[i]);
            sum += candidates[i];
            backTravel(candidates, i);//递归
            path.pollLast();//回溯
            sum -= candidates[i];
        }
    }
    public List> combinationSum(int[] candidates, int target) {
        T = target;
        sum = 0;
        len = candidates.length;
        backTravel(candidates, 0);
        return result;
    }
}

二、40. 组合总和 II

题目链接：40. 组合总和 II

题目描述：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

算法分析：

这道题的做法跟上一道题类似，不过要注意的时要对于重复的组合进行去重操作。

具体去重操作为：

首先回溯之前对数组进行排序，如此相同的元素会放在一起。

然后再横向遍历数组是，对同一个元素重复出现在同一个位置去重（注意同一个元素出现在不同位置时不去重）。

代码如下：

class Solution {
    List>result = new ArrayList<>();//存放所有组合的结果集
    LinkedList path = new LinkedList<>();//搜索每种组合
    int T;
    int sum;
    int len;
    public void backTravel(int[] candidates, int startIndex) {
        if(sum == T) {//如果总和等于目标值，将组合放入结果集返回
            result.add(new LinkedList<>(path));
            return;
        }else if(sum > T) return;//如果总和大于目标值，直接返回
 
        for(int i = startIndex; i < len; i++) {//从起始下标横向遍历数组
            if(i > startIndex && candidates[i] == candidates[i - 1]) continue;//一个元素重复出现在同一位置时，进行去重
            path.add(candidates[i]);
            sum += candidates[i];
            backTravel(candidates, i + 1);//递归
            path.removeLast();//回溯
            sum -= candidates[i];
        }
    }
    public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        T = target;
        sum = 0;
        len = candidates.length;
        backTravel(candidates, 0);
        return result;
 
    }
}

三、131. 分割回文串

题目链接：131. 分割回文串

题目描述：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

算法分析：

做法跟上两道题类似，也是用回溯算法不过在对每种方案添加元素（字符串时），要判断一下该子串是否是回文串。

所以我们还要在上面的基础上增加一个判断子串是否是回文串的方法。

具体待码如下：

class Solution {
    List> result = new ArrayList<>();//用来存放每种方案的结果集
    LinkedList path = new LinkedList<>();//用来遍历每种方案
    int len;//字符串的长度
    public boolean isPartition(String s, int left, int right) {//判断字串是否是回文串
        while(left <= right) {
            if(s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
    public void backTravel(String s, int startIndex) {
        if(startIndex == len) {//如果起始下标等于字符串的长度，说明有一个分割方案了，将方案放入结果集，然后返回
            result.add(new LinkedList<>(path));
            return;
        }else if(startIndex > len) return;//如果起始下标大于字符串长度，说明没有分割方案，直接返回。
        for(int i = startIndex; i < len; i++) {//遍历从起始下标到结尾的子串，并判断从起始下标到i的字串是否是回文串
            if(isPartition(s, startIndex, i) != true) continue;//如果不是回文串，继续下一层for循环。
            path.add(s.substring(startIndex, i + 1));
            backTravel(s, i + 1);//递归
            path.removeLast(); //回溯
        }
    }
    public List> partition(String s) {
        len = s.length();
        backTravel(s, 0);
        return result;
 
    }
}

总结

回溯时，我们不要只会对整数数组回溯，还要会对各种数组进行回溯。