【算法训练-回溯算法 三】【回溯算法最佳实践】括号生成、复原IP地址

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【回溯算法】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

括号生成

终于轮到解这两道高频题了

题干

解题思路

原解题思路括号问题可以简单分成两类，一类是括号的合法性判断 ，一类是合法括号的生成。对于括号合法性的判断，主要是借助「栈」这种数据结构，而对于括号的生成，一般都要利用回溯递归的思想。

有关括号问题，你只要记住以下性质，思路就很容易想出来：

1. 一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。
2. 对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。

如果不跟你说这个性质，可能不太容易发现，但是稍微想一下，其实很容易理解，因为从左往右算的话，肯定是左括号多嘛，到最后左右括号数量相等，说明这个括号组合是合法的。

算法输入一个整数 n，让你计算 n 对儿括号能组成几种合法的括号组合，可以改写成如下问题：

现在有 2n 个位置，每个位置可以放置字符 ( 或者 )，组成的所有括号组合中，有多少个是合法的？

这个命题和题目的意思完全是一样的对吧，那么我们先想想如何得到全部 2^(2n) 种组合，然后再根据我们刚才总结出的合法括号组合的性质筛选出合法的组合，不就完事儿了？那么对于我们的需求，如何打印所有括号组合呢，伪代码如下

void backtrack(int n, int i, string& track) {
    // i 代表当前的位置，共 2n 个位置
    // 穷举到最后一个位置了，得到一个长度为 2n 组合
    if (i == 2 * n) {
        print(track);
        return;
    }
    // 对于每个位置可以是左括号或者右括号两种选择
    for choice in ['(', ')'] {
        track.push(choice); // 做选择
        // 穷举下一个位置
        backtrack(n, i + 1, track);
        track.pop(choice); // 撤销选择
    }
}

那么，现在能够打印所有括号组合了，如何从它们中筛选出合法的括号组合呢？很简单，加几个条件进行「剪枝」就行了。

对于 2n 个位置，必然有 n 个左括号，n 个右括号，所以我们不是简单的记录穷举位置 i，而是用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号，这样就可以通过刚才总结的合法括号规律进行筛选了

代码实现

给出代码实现基本档案

基本数据结构：数组

辅助数据结构：无

算法：回溯算法

技巧：无

import java.util.*;
public class Solution {
    // 定义结果集和路径
    private ArrayList<String> result = new ArrayList<String>();
    StringBuilder path = new StringBuilder();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        if (n < 0) {
            return new  ArrayList<String>();
        }
        // 左右括号剩余数当做入参传入
        backTrack( n,  n);
        return result;
    }
    private void backTrack(int leftRemaind, int rightRemaind) {
        // 1 超量使用括号不合法，则剪枝
        if (leftRemaind < 0 || rightRemaind < 0) {
            return;
        }
        // 2 如果左括号剩余数量大于右括号，则认为右括号在前面过多使用，无法闭合，剪枝
        if (leftRemaind > rightRemaind) {
            return;
        }
        // 3 如果左右括号同时消耗完，证明到了叶子节点，结算
        if (leftRemaind == 0 && rightRemaind == 0) {
            result.add(path.toString());
            return;
        }
        // 4 左边括号回溯
        path.append('(');
        backTrack(leftRemaind - 1, rightRemaind);
        path.deleteCharAt(path.length() - 1);
        // 5 右边括号回溯
        path.append(')');
        backTrack(leftRemaind, rightRemaind - 1);
        path.deleteCharAt(path.length() - 1);
    }
}

复杂度分析

下面是对给定代码的时间和空间复杂度分析：

时间复杂度：

• 生成所有可能的括号组合需要进行回溯操作，因此时间复杂度取决于生成的括号字符串的数量。
• 最坏情况下，可以生成的括号字符串数量为卡特兰数的第 n 项，约为 O(4^n / (n^(3/2)))，这是因为每个位置都有两种选择，左括号或右括号，总共 2^(2n) 种组合。
• 因此，时间复杂度为 O(4^n / (n^(3/2)))。

空间复杂度：

• 空间复杂度主要取决于递归调用的栈空间和存储结果的数据结构。
• 在递归调用中，栈的最大深度不会超过 n，因为每一步都减少一个左括号或右括号，最多递归 n 层。因此，栈空间的空间复杂度为 O(n)。
• 存储结果的 result 列表和 path 字符串的长度也会受到影响，但在最坏情况下，result 中的字符串数量为卡特兰数的第 n 项，所以结果列表的空间复杂度也可以视为 O(4^n / (n^(3/2)))。path 字符串的最大长度为 2n，所以它的空间复杂度是 O(n)。
• 因此，总的空间复杂度是 O(n) + O(4^n / (n^(3/2)))。

需要注意的是，在实际应用中，生成括号字符串的数量通常较小，因此代码的实际运行时间和空间占用可能会更加可控。

对于递归相关的算法，时间复杂度这样计算（递归次数）*（递归函数本身的时间复杂度）

复原IP地址【MID】

元素无重不可复选，且不可重排序【子集组合框架】再来一道复原IP地址

题干

解题思路

原解题地址回溯算法事实上就是在一个树形问题上做深度优先遍历，因此 首先需要把问题转换为树形问题。

在画树形图的过程中，你一定会发现有些枝叶是没有必要的，把没有必要的枝叶剪去的操作就是剪枝，在代码中一般通过 break 或者 contine 和 return （表示递归终止）实现。分析剪枝条件：

1. 一开始，字符串的长度小于 4 或者大于 12 ，一定不能拼凑出合法的 ip 地址（这一点可以一般化到中间结点的判断中，以产生剪枝行为）；
2. 每一个结点可以选择截取的方法只有 3 种：截 1 位、截 2 位、截 3 位，因此每一个结点可以生长出的分支最多只有 3 条分支，根据截取出来的字符串判断是否是合理的 ip 段，这里写法比较多，可以先截取，再转换成 int ，再判断。
3. 由于 ip 段最多就 4 个段，因此这棵三叉树最多 4 层，这个条件作为递归终止条件之一；
4. 每一个结点表示了求解这个问题的不同阶段，需要的状态变量有：splitTimes：已经分割出多少个 ip 段；begin：截取 ip 段的起始位置；path：记录从根结点到叶子结点的一个路径（回溯算法常规变量，是一个栈）；res：记录结果集的变量，常规变量。

接下来套用回溯模版来写一下

代码实现

给出代码实现基本档案

基本数据结构：数组

辅助数据结构：无

算法：回溯算法

技巧：无

import java.util.*;
public class Solution {
    // 1 定义结果集和路径
    private List<String> result = new ArrayList<String>();
    private List<String> path = new ArrayList<>();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    public List<String> restoreIpAddresses(String s) {
        // 1 字符串合法性判断
        if (s.length() == 0 || s.length() < 4 || s.length() > 12) {
            return new ArrayList<String>();
        }
        backTrack(s, 0);
        return result;
    }
    // 构造的是子集树
    private void backTrack(String s, int start) {
        // 剪枝1：暴力遍历结束,指针溢出了
        if (s.length() < start) {
            return;
        }
        // 剪枝2：可用字符太多
        if (s.length() - start > (4 - path.size()) * 3) {
            return;
        }
        // 剪枝3：可用字符太少
        if (s.length() - start < 4 - path.size()) {
            return;
        }
        // 叶子节点，路径添加
        if (path.size() == 4) {
            result.add(String.join(".", path));
            return;
        }
        // 选择列表
        for (int i = start; i < s.length() && i < start + 3; i++) {
            // 1 截取子串,从当前位置出发，横向的3种可能性
            String subStr = s.substring(start, i + 1);
            // 2 如果子串不满足条件，则不添加到路径上
            if (!isValidSubIpAddress(subStr)) {
                continue;
            }
            // 3 前进与回溯，子集问题，前面用过的重复可能不再使用，所以start为i+1
            path.add(subStr);
            backTrack(s, i + 1);
            path.remove(path.size() - 1);
        }
    }
    // 判断一段字符串是否为合法IP段
    private boolean isValidSubIpAddress(String subStr) {
        // 1 如果字符串截取的长度不满足则为false
        int subIpAddressLen = subStr.length();
        if (subIpAddressLen < 1 || subIpAddressLen > 3 ) {
            return false;
        }
        // 2 如果长度大于1位，则第1位不能为0，也就是不能有前导0
        if (subIpAddressLen > 1 && subStr.charAt(0) == '0') {
            return false;
        }
        // 3 值验证，值必须大于等于0且小于等于255
        int sum = 0;
        for (int i = 0; i < subStr.length(); i++) {
            sum = sum * 10 +  subStr.charAt(i) - '0';
            if (sum > 255) {
                return false;
            }
        }
        return true;
    }
}

这里的backTrack(s, i + 1);与子集问题有异曲同工之妙，都是不可复选的意思。这里表示字符串下一层只能往后选，子集里的则表示用过的元素不能再被使用

1 剪枝分析：剩余字符太少

if (s.length() - begin < (4 - path.size())) return;

让我们通过一个示例来说明代码中的这部分剪枝逻辑。

假设输入字符串 s 为 “25525511135”，我们希望生成合法的 IP 地址。在这个示例中，s 的长度为 11 个字符。

• 初始时，begin 为 0，path 为空，即 path.size() 为 0。
• 我们需要生成 4 个IP地址段。
• 假设我们已经生成了 path 中的部分IP地址段。

在这个时刻，剪枝逻辑 if (s.length() - begin < (4 - path.size())) return; 发挥作用。我们可以通过具体的示例来解释：

• path.size() 是已经生成的 IP 地址段的数量，假设为 k。
• (4 - path.size()) 表示剩下需要生成的IP地址段数量，即 4 - k。
• s.length() - begin 表示从当前 begin 位置开始的剩余字符串的长度。

剪枝条件的含义是，如果剩余的字符串长度不足以填充需要生成的剩余IP地址段，那就没有必要继续搜索，因为在这种情况下，无法生成合法的IP地址。

对于示例 “25525511135”：

• 当 begin 为 0 时，已经生成 0 个IP地址段，需要生成 4 个，因此 (4 - path.size()) 为 4。
• 剩余的字符串长度为 11（整个输入字符串的长度） - 0（当前位置 begin） = 11。
• 因此，s.length() - begin 大于 (4 - path.size())，即 11 > 4，这意味着可以继续搜索下一个IP地址段。

这个剪枝条件的目的是在每个搜索步骤中，确保剩余的字符串足够填充所有需要生成的IP地址段。如果不满足这个条件，就没有必要继续搜索，因为无法生成合法的IP地址。

2 剪枝分析：剩余字符太多

if (s.length() - begin > (4 - path.size()) * 3) return;

这行代码是用于进一步剪枝的逻辑。它的目的是确保剩余的字符串长度不会过长，以至于无法生成合法的 IP 地址。让我通过一个示例来说明这部分剪枝逻辑：

假设输入字符串 s 为 “25525511135”，我们依然希望生成合法的 IP 地址。

• 初始时，begin 为 0，path 为空，即 path.size() 为 0。
• 我们需要生成 4 个 IP 地址段。

在这个示例中，我们将关注这部分剪枝逻辑 if (s.length() - begin > (4 - path.size()) * 3) return;。我们可以通过具体的示例来解释：

• path.size() 是已经生成的 IP 地址段的数量，假设为 k。
• (4 - path.size()) 表示剩下需要生成的 IP 地址段数量，即 4 - k。
• s.length() - begin 表示从当前 begin 位置开始的剩余字符串的长度。

剪枝条件的含义是，如果剩余的字符串长度超过了填充需要生成的剩余 IP 地址段所需的最大字符数，那就没有必要继续搜索，因为在这种情况下，也无法生成合法的 IP 地址。

对于示例 “25525511135”：

• 当 begin 为 0 时，已经生成 0 个 IP 地址段，需要生成 4 个，因此 (4 - path.size()) 为 4。
• 剩余的字符串长度为 11（整个输入字符串的长度） - 0（当前位置 begin） = 11。

剪枝条件 if (s.length() - begin > (4 - path.size()) * 3) 表示如果剩余字符串长度大于 (4 - path.size()) * 3，就没有必要继续搜索。因为每个 IP 地址段最多有 3 个字符，所以 (4 - path.size()) * 3 表示需要填充剩余 IP 地址段所需的最大字符数。如果剩余字符串长度超过这个最大字符数，那么就不可能生成合法的 IP 地址。

在这个示例中，11 < 4 * 3 成立，所以搜索会继续。但如果 s 长度更长，例如 “255255111356789”，那么 s.length() - begin 将大于 (4 - path.size()) * 3，并且搜索会被剪枝，因为不可能生成合法的 IP 地址。

复杂度分析