13.3 回溯法解决其他类型的问题

若一个问题每一步有多个选项, 并且需要列出所有解, 那么就适用于回溯法.

13.3.1 问题85: 生成匹配括号

LCR 085. 括号生成

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

13.3.1.1 分析&题解

左右括号各n个, 一共需要2n个括号, 每步有两个选择, 适用于回溯法.

特殊条件: 左括号要比右括号优先生成.

func generateParenthesis(n int) []string {
    res := []string{}
    helper(n, n, "", &res)
    return res
}

func helper(left, right int, par string, res *[]string) {
    // 生成完毕
    if left == 0 && right == 0 {
        *res = append(*res, par)
        return 
    }

    // 左括号
    if left > 0 {
        helper(left-1, right, par+"(", res)
    }

    // 右括号
    if left < right {
        helper(left, right-1, par+")", res)
    }
}

13.3.2 问题86: 分割回文子串

LCR 086. 分割回文串

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

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

示例 1：

输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

示例 2：

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

示例 3：

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

提示：

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

13.3.2.1 分析&题解

解决此问题需要很多步, 每步有多个字符可选, 需要找出所有的组合, 适用于回溯法.

当从i开始寻找子串, 若[i, j]是回文那么就从i+1开始, 直到字符串末尾结束.

func partition(s string) [][]string {
    res := [][]string{}
    helper(s, 0, &[]string{}, &res)
    return res
}

func helper(s string, start int, sub *[]string, res *[][]string) {
    // 寻找完毕
    if start == len(s) {
        tmp := make([]string, len(*sub))
        copy(tmp, *sub)
        *res = append(*res, tmp)
        return 
    } 
    
    for i := start; i < len(s); i++ {
        if isPalidrome(s, start, i) {
            *sub = append(*sub, s[start:i+1])
            helper(s, i+1, sub, res)
            // 回溯
            *sub = (*sub)[:len(*sub)-1]
        }
    }
}

func isPalindrome(s string, i, j int) bool {
    start, end := i, j
    for start < end {
        if s[start] != s[end] {
            return false
        }

        start++
        end--
    }
    return true
}

13.3.3 问题87: 恢复IP地址

LCR 087. 复原 IP 地址

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

示例 1：

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

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

提示：

• 0 <= s.length <= 3000
• s 仅由数字组成

13.3.3.1 分析&题解

对于第i个字符来说, 当前有两个选择:

• 继续添加字符: 添加字符后必须是合法数字(不以0开头)
• 添加分隔符.: 分隔符数量小于3个,才可以添加

func restoreIpAddresses(s string) []string {
    res := []string{}
    helper(s, 0, 0, "", "", &res)
    return res
}

func helper(s string, idx, segI int, seg, ip string, res *[]string) {
    // 恢复完成
    if idx == len(s) && segI == 3 && isValid(seg) {
        *res = append(*res, ip+seg)
        return 
    }

    if idx < len(s) {
        // 添加字符
        c := s[idx]
        newSeg := seg + string(c)
        if isValid(newSeg) {
            helper(s, idx+1, segI, newSeg, ip, res)
        }

        // 添加分隔符
        if len(seg) > 0 && segI < 3 {
            helper(s, idx+1, segI+1, string(c), ip+seg+".", res)
        }
    }
}

func isValid(s string) bool {
    n, _ := strconv.Atoi(s)
    return n <= 255 && (s == "0" || s[0] != '0')
}

Reference

1. 剑指Offer（专项突破版）