[Java恶补day54] 整理模板·考点十二【回溯】

【问题引入】

1. 问题描述
   生成长为n的字符串，第一个字符在某几个字母中选择，第二个字符在另外几个字母中选择，以此类推，如何实现？
2. 解
   原问题：构造长为n的字符串
   👇
   枚举一个字母
   👇
   子问题：构造长为n-1的字符串
   子问题、原问题是相似的，从原问题到子问题的过程适合用递归解决

【回溯基本概念】
回溯有一个增量构造答案的过程，该过程通常用递归实现

【回溯套路】【回溯问题（回溯三问）、DP问题的模板】⭐
用path数组记录路径上的字母

1. 当前操作？枚举$path[i]$要填入的字母
2. 子问题？构造字符串$\ge i$的部分
3. 下一个子问题？构造字符串$\ge i+1$的部分

【回溯分类】

1. 子集型回溯
   ①含义
   每个元素都可以选/不选
   ②例子
   0/1背包问题
   ③解题思路（站在输入的角度）
   每个数可以在子集中，也可以不在子集中，叶子是答案
   a. 当前操作？枚举第$i$个数选不选
   b. 子问题？从下标$\ge i$的数字中构造子集
   c. 下一个子问题？从下标$\ge i+1$的数字中构造子集
   ④解题思路（站在答案的角度）
   枚举第一个数选谁，枚举第二个数选谁，以此类推，每个节点都是答案
   a. 当前操作？枚举一个下标$j\ge i$的数字，加入path
   b. 子问题？从下标$\ge i$的数字中构造子集
   c. 下一个子问题？从下标$\ge j+1$的数字中构造子集

2. 组合型回溯
   ①含义

②例子

3. 排列型回溯
   ①含义

②例子

131. 分割回文串

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

示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

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

知识点：
字符串、动态规划、回溯

解：
时间复杂度：$O(n\ast 2^n)$。判断回文需要$O(n)$，总共递归$2^n$次，每次要么选要么不选，共两个选择
空间复杂度：$O(n)$。

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(0, 0, s, path, res);
        return res;
    }

    // 考虑下标i的字母后面的逗号怎么选
    private void dfs(int i, int start, String s, List<String> path, List<List<String>> res) {
        //若划分完毕，则返回答案
        if (i == s.length()) {
            //复制path
            res.add(new ArrayList<>(path));
            return;
        }
        //下标i和i+1之间不选逗号
        if (i < s.length() - 1) {
            dfs(i + 1, start, s, path, res);
        }
        //下标i和i+1之间选逗号
        if (isPalindrome(s, start, i)) {
            //逗号前的部分加入path
            path.add(s.substring(start, i + 1));
            //考虑i+1后面的逗号怎么选
            dfs(i + 1, i + 1, s, path, res);
            //恢复现场
            path.removeLast();
        }
    }

    //判断是否是回文字符串
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

参考：
1、灵神题解