回溯有很多比较难的问题，这里我们看两个，整体来说这两个只是处理略复杂，还不是最难的问题，感兴趣的同学可以继续研究。

关卡名	继续看回溯问题	我会了✔️
内容	1.复习递归和N叉树，理解相关代码是如何实现的	✔️
	2.理解回溯到底怎么回事	✔️
	3.掌握如何使用回溯来解决二叉树的路径问题	✔️

1. 复原IP地址

这也是一个经典的分割类型的回溯问题。LeetCode93.有效IP地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0. 011. 255 .245"、"192.168.1.312" 和 "192.168@1.1" 是无效IP地址。给定一个只包含数字的字符串s，用以表示一个IP地址，返回所有可能的有效IP地址，这些地址可以通过在s中插入 '.' 来形成。你不能重新排序或删除s中的任何数字。你可以按任何顺序返回答案。

示例1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

该问题的思路与与前面的分割回文串基本一致，也是切割问题。回溯的第一步就是使用枚举将所有可能性搜出来,找到一个符合要求的就先切下来，后面的部分继续进行枚举和切割，如果到了最后发现不符合要求，则开始回溯。 本题的难度明显比上一题要大，主要是判断是否合法的要求更高了，比如第一个元素我们可以截取2、25、255、2552，很显然到了2552之后就不合法了，此时就要回溯。后面也一样，假如我们第一层截取的是2，第二层就从”5525511135“中截取，此时可以有5，55，552，显然552已经不合法了，依次类推。画出图来就如下所示：

当然这里还要判断是0的情况等等，在字符串转换成数字一章，我们讲解了很多种要处理的情况，为此我们可以写一个方法单独来执行相关的判断。代码如下：

// 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        // 0开头的数字不合法
        if (s.charAt(start) == '0' && start != end) { 
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
        // 遇到⾮数字字符不合法
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { 
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }

另外，IP地址只有四段，不是无限分割的，因此本题只会明确的分成4段，不能多也不能少。所以不能用切割线切到最后作为终止条件，而是分割的段数到了4就必须终止。考虑到我们构造IP地址时还要手动给添加三个小数点，所以我们用变量pointNum来表示小数点数量，pointNum为3说明字符串分成了4段了。 要手动添加一个小数点，这要增加一个位置来存储，所以下一层递归的startIndex要从i+2开始。其他的主要工作就是递归和回溯的过程了。这里的撤销部分要注意将刚刚加入的分隔符删掉，并且pointNum也要-1，完整代码如下：

class Solution {
    static final int SEG_COUNT = 4;
    List<String> ans = new ArrayList<String>();
    int[] segments = new int[SEG_COUNT];

    public List<String> restoreIpAddresses(String s) {
        segments = new int[SEG_COUNT];
        dfs(s, 0, 0);
        return ans;
    }

    public void dfs(String s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
        if (segId == SEG_COUNT) {
            if (segStart == s.length()) {
                StringBuffer ipAddr = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr.append(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr.append('.');
                    }
                }
                ans.add(ipAddr.toString());
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (segStart == s.length()) {
            return;
        }

        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        if (s.charAt(segStart) == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
            return;
        }

        // 一般情况，枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }
}

class RestoreIpAddresses:
    def __init__(self):
        self.result = []

    def restoreIpAddresses(self, s: str) -> List[str]:
        '''
        本质切割问题使用回溯搜索法，本题只能切割三次，所以纵向递归总共四层
        因为不能重复分割，所以需要start_index来记录下一层递归分割的起始位置
        添加变量point_num来记录逗号的数量[0,3]
        '''
        self.result.clear()
        if len(s) > 12: return []
        self.backtracking(s, 0, 0)
        return self.result

    def backtracking(self, s: str, start_index: int, point_num: int) -> None:
        # Base Case
        if point_num == 3:
            if self.is_valid(s, start_index, len(s)-1):
                self.result.append(s[:])
            return
        # 单层递归逻辑
        for i in range(start_index, len(s)):
            # [start_index, i]就是被截取的子串
            if self.is_valid(s, start_index, i):
                s = s[:i+1] + '.' + s[i+1:]
                self.backtracking(s, i+2, point_num+1)  # 在填入.后，下一子串起始后移2位
                s = s[:i+1] + s[i+2:]    # 回溯
            else:
                # 若当前被截取的子串大于255或者大于三位数，直接结束本层循环
                break
    
    def is_valid(self, s: str, start: int, end: int) -> bool:
        if start > end: return False
        # 若数字是0开头，不合法
        if s[start] == '0' and start != end:
            return False
        if not 0 <= int(s[start:end+1]) <= 255:
            return False
        return True

class RestoreIpAddresses {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法，直接结束本层循环
        }
    }
    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

2. 电话号码问题

LeetCode17.电话号码组合问题，也是热度非常高的一个题目，给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母，9对应四个字母。

示例1：
输入：digits = "2|  3 4567"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

我们说回溯仍然会存在暴力枚举的情况，这个题就很典型，例如如果输入23，那么，2就有 a、b、c三种情况，3有d、e、f三种情况。组合一下就一共就有3*3=9种，如果是233，那么就是27种。 这里要注意的9对应4个字母，而1则没有，那该怎么建立字母和数字之间的映射呢？我们用一个数组来保存，而不写一堆的if else。而为了保证遍历时index也恰好与数组的索引一致，我们按照如下的方式来定义数组： String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 接下来我们就用回溯来解决n层循环的问题，输入23对应的树就是这样的：

树的深度就是输入的数字个数，例如输入23，树的深度就是2。而所有的叶子节点就是我们需要的结果["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。所以这里的终止条件就是，如果当前执行的index 等于输入的数字个数（digits.size）了。 使用for循环来枚举出来，然后循环体内就是回溯过程了。基本实现过程如下：

class LetterCombinations {
    List<String> list = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
        //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
     
        backTracking(digits, numString, 0);
        return list;
    }
 
    //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();
 
    //比如digits如果为"23",num 为0，则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
        //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

class LetterCombinations:
    def __init__(self):
        self.answers: List[str] = []
        self.answer: str = ''
        self.letter_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }

    def letterCombinations(self, digits) :
        self.answers.clear()
        if not digits: return []
        self.backtracking(digits, 0)
        return self.answers
    
    def backtracking(self, digits, index) :
        # 回溯函数没有返回值
        if index == len(digits):    # 当遍历穷尽后的下一层时
            self.answers.append(self.answer)
            return 
        # 单层递归逻辑  
        letters: str = self.letter_map[digits[index]]
        for letter in letters:
            self.answer += letter   # 处理
            self.backtracking(digits, index + 1)    # 递归至下一层
            self.answer = self.answer[:-1]  # 回溯

class LetterCombinations {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> combinations;
        if (digits.empty()) {
            return combinations;
        }
        unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string combination;
        backtrack(combinations, phoneMap, digits, 0, combination);
        return combinations;
    }

    void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
        if (index == digits.length()) {
            combinations.push_back(combination);
        } else {
            char digit = digits[index];
            const string& letters = phoneMap.at(digit);
            for (const char& letter: letters) {
                combination.push_back(letter);
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};

3. 括号生成问题

本题是一道非常典型的回溯问题，LeetCode22.数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

要解决该问题，我们首先要明确一个问题，左右括号什么时候可以获得。我们知道左括号出现的数量一定等于n，观察题目给的示例，只要剩余左括号的数量大于0，就可以添加"("，例如"("、"(()"、”(()(“、”()((“都是可以的，因为我们只要再给加几个右括号就行，例如可以将其变成"()"、"(())"、”(()()“、”()(())“。 那添加右括号的要求呢？结论是：序列中左括号的数量必须大于右括号的数量，例如上面的"("、"(()"、”(()(“、”()((“，都可以，但是如果")"、"())"、”)()(“、”()((“就不可以了，此时的情况都是右括号数量大于等于左括号。所以我们可以得到两条结论

1. 只要剩余左括号的数量大于0，就可以添加"("。
2. 序列中左括号的数量必须大于右括号的数量才可以添加"("，并且")"的剩余数量大于0.

接下来看如何用回溯解决，我们将添加"("视为left，将")"视为right，这样"("和")"各可以出现n次。我们以n=2为例画一下的图示：

图中红叉标记的位置是左括号大于有括号了，不能再向下走了，这个操作也称为剪枝。通过图示，可以得到如下结论：

• 当前左右括号都有大于 0 个可以使用的时候，才产生分支，否则就直接停止。
• 产生左分支的时候，只看当前是否还有左括号可以使用；
• 产生右分支的时候，除了要求还有右括号，还要求剩余右括号数量一定大于左括号的数量；
• 在左边和右边剩余的括号数都等于 0 的时候结束。

而且，从上图可以看到，不管是剪枝还是得到一个结果，返回的过程仍然可以通过回溯来实现：

class GenerateParenthesis {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
    
    /**
     * @param ans 当前递归得到的结果
     * @param cur 当前的括号串
     * @param open   左括号已经使用的个数
     * @param close  右括号已经使用的个数
     * @param max    序列长度最大值
     */
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        //本题需要两次回溯，比较少见的情况
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

class GenerateParenthesis:
    def generateParenthesis(self, n) :
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()

        backtrack([], 0, 0)
        return ans

class GenerateParenthesis {
    void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {
        if (cur.size() == n * 2) {
            ans.push_back(cur);
            return;
        }
        if (open < n) {
            cur.push_back('(');
            backtrack(ans, cur, open + 1, close, n);
            cur.pop_back();
        }
        if (close < open) {
            cur.push_back(')');
            backtrack(ans, cur, open, close + 1, n);
            cur.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
};

4. 通关文牒

本文讲解了很多经典的回溯问题，将上面的内容理解清楚即可.