【算法】回溯算法（一）：从一道 IP 题到万能模板

文章信息

• 原文链接：https://jiayq.blog.csdn.net/article/details/164337400
• 发布时间：2026-09-03 17:30:53
• 标签：#Golang, #算法, ##算法讲解, ##Go

---

【算法】回溯算法（一）：从一道 IP 题到万能模板

摘要

回溯系列第一篇，入门。从「复原 IP 地址」这道经典题出发，完整走一遍回溯的标准建模流程：把约束拆干净 → 画决策树 → 套三要素 → 三层剪枝 → 写代码 → 踩题内小坑。最后沉淀出一份可复用的回溯模板——八字口诀「判终、砍支、循环三连」，加上决策三形态和三验证。本篇是纯入门，一次车都不翻；翻车实录在第二篇，五个坑一个比一个深。

说明，以下环境基于 go1.21+，题目均来自 LeetCode。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode

系列篇目：

• 一、从一道 IP 题到万能模板（本篇）
• 二、五个坑与一次验收——决策、切片与去重
• 三、三记重锤与 N 皇后——记忆化、状态设计与三层漏斗

1. 起点：复原 IP 地址

1.1 问题描述

题目很简单，一句话：

给定一个只包含数字的字符串 s，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 . 来形成。不能重新排序或删除 s 中的任何数字。

几个示例：

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

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

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

说白了，就是在字符串里找 3 个位置插点，把原串切成 4 段，要求每段都是一个合法的 IPv4 地址段。

1.2 问题分析：先把约束拆干净

拿到这道题，先别急着写代码，把「合法 IP 段」的定义拆成可执行的条件。一段数字合法，必须同时满足 下面 4 条：

约束	说明	反例
长度 1 ∼ 3 1 \sim 3 1∼3 位	每段最多 3 个数字	4 位数字必然超过 255
数值 0 ∼ 255 0 \sim 255 0∼255	越界非法	312 非法
无前导零	长度大于 1 时首字符不能是 0	01、00 非法，但 0 合法
字符恰好用完	4 段拼起来必须等于原串	不能有剩余字符，也不能不够分

由最后一条还能推出一个全局剪枝 ：合法输入的长度必须在 [ 4 , 12 ] [4, 12] [4,12] 之间。最短是 0.0.0.0（4 个字符），最长是 255.255.255.255（12 个字符）。长度不在这个区间的输入，连回溯都不用进，直接返回空。

打个比方，这个约束表就是「裁判规则」：回溯过程中每切出一段，裁判就照着表过一遍，任何一条不满足，这条分支立刻毙掉。

1.3 回溯思路：把问题画成一棵树

回溯的本质就是决策树的深度优先遍历（DFS） 。这道题的决策过程是：每一层决定一段 IP，每层最多 3 个分支（取 1 位、2 位、3 位），树的最大深度固定是 4。

以 s = "25525511135" 为例，决策树长这样（? 表示还没填的段，虚线是走不通被剪掉的分支）：

2

25

255

255

11

111

135

35

剩余10字符 > 3×3上限

子分支全部越界或超长

25525511135

2.?.?.?

25.?.?.?

255.?.?.?

255.255.?.?

255.255.11.?

255.255.111.?

255.255.11.135 ✓

255.255.111.35 ✓

剪枝 ✗

剪枝 ✗

三个根分支的命运各不相同：

• 2 开头：只用了 1 个字符，剩余 10 个字符要塞进 3 段，但 3 段最多容纳 3 × 3 = 9 3 \times 3 = 9 3×3=9 个字符，可行性剪枝 直接整支剪掉
• 25 开头：第 2 段取 525 数值越界，取 5/52 后续也分配不下去，所有子分支都被剪光
• 255 开头：一路合法往下走，第 3 段取 11 配第 4 段 135、取 111 配第 4 段 35，收获两个合法解

1.4 回溯三要素

套回溯的标准框架，三要素在这道题里的对应关系：

要素	本题对应
路径	已经确定的段列表 path，比如 ["255", "255"]
选择列表	从当前位置 start 开始，取 1 位、2 位或 3 位子串
结束条件	len(path) == 4 && start == len(s)，凑够 4 段且字符恰好用完

这里有个最容易写错的点 ：结束条件是「与」不是「或」。len(path) == 4 只说明段数够了，还必须检查 start == len(s) 确认字符刚好用完。比如 "25525511"，切出 2.5.5.2 后还剩 5511 没用，这种组合必须丢弃。反过来，字符用完了但段数不够 4，同样作废。

1.5 三层剪枝

剪枝是回溯的精髓，这道题可以做三层：

1. 全局剪枝 ：len(s) < 4 || len(s) > 12，直接返回空，搜索都不用开始。
2. 可行性剪枝 ：设剩余字符数为 r e m a i n remain remain，还需填的段数为 n e e d need need，则必须满足 n e e d ≤ r e m a i n ≤ 3 × n e e d need \le remain \le 3 \times need need≤remain≤3×need。剩余字符比段数还少，肯定不够分；剩余字符超过 3 × n e e d 3 \times need 3×need，肯定装不下。这个剪枝能砍掉大量注定失败的分支。
3. 合法性剪枝 ：切出的段做两个检查——前导零（len(seg) > 1 && seg[0] == '0'）和数值上限（> 255）。

否，继续搜索

是

否

是

试下一个 length

否，试下一个

是，break

是

是

否

否，剪枝

进入 backtrack(start, path)

path 凑够 4 段？

剩余字符够分
且装得下？

取段长度 length
从 1 到 3 逐个试

start + length
超出串长？

段合法？
无前导零且 ≤ 255

做选择
path 追加 seg

递归下一层
backtrack(start + length, path)

撤销选择
path 弹出 seg

本次调用结束
返回上一层

字符刚好用完？

✓ 收集结果

✗ 丢弃

顺着主干从上往下读，就是一次完整的搜索过程：没凑够 4 段就先过剪枝检查，剪不掉就逐个长度试探，段合法就执行「做选择 → 递归 → 撤销」三连，再回头试下一个长度；凑够 4 段则走右侧出口，字符刚好用完才收集结果。

2. Go 实现

完整代码，可直接复制运行：

package main

import (
	"fmt"
	"strconv"
	"strings"
)

// restoreIpAddresses 复原 IP 地址：回溯法
func restoreIpAddresses(s string) []string {
	var result []string
	// 全局剪枝：合法 IP 长度范围 [4, 12]
	if len(s) < 4 || len(s) > 12 {
		return result
	}

	// backtrack: start 是当前处理到的下标，path 是已确定的段
	var backtrack func(start int, path []string)
	backtrack = func(start int, path []string) {
		// 终止条件：凑够 4 段，且字符恰好用完（两个条件缺一不可）
		if len(path) == 4 {
			if start == len(s) {
				result = append(result, strings.Join(path, "."))
			}
			return
		}

		// 可行性剪枝：剩余字符必须能填满剩余段，且不超上限
		remain := len(s) - start
		need := 4 - len(path)
		if remain < need || remain > 3*need {
			return
		}

		// 每段尝试取 1~3 位
		for length := 1; length <= 3; length++ {
			if start+length > len(s) {
				break
			}
			seg := s[start : start+length]
			// 合法性剪枝：前导零 / 超过 255 直接跳过
			if !isValidSegment(seg) {
				continue
			}
			// 做选择
			path = append(path, seg)
			// 进入下一层
			backtrack(start+length, path)
			// 撤销选择
			path = path[:len(path)-1]
		}
	}

	backtrack(0, []string{})
	return result
}

// isValidSegment 判断一段数字是否合法
func isValidSegment(seg string) bool {
	// 前导零检查："0" 合法，"01"/"00" 非法
	if len(seg) > 1 && seg[0] == '0' {
		return false
	}
	// 数值范围检查：0 ~ 255
	val, _ := strconv.Atoi(seg)
	return val <= 255
}

func main() {
	testCases := []string{
		"25525511135",    // 常规用例
		"0000",           // 全零
		"101023",         // 多解
		"1111",           // 唯一解
		"010010",         // 前导零陷阱
		"12345678901234", // 超长剪枝
	}
	for _, s := range testCases {
		fmt.Printf("输入: %-16s 输出: %v\n", s, restoreIpAddresses(s))
	}
}

运行结果：

输入: 25525511135      输出: [255.255.11.135 255.255.111.35]
输入: 0000             输出: [0.0.0.0]
输入: 101023           输出: [1.0.10.23 1.0.102.3 10.1.0.23 10.10.2.3 101.0.2.3]
输入: 1111             输出: [1.1.1.1]
输入: 010010           输出: [0.10.0.10 0.100.1.0]
输入: 12345678901234   输出: []

这道题内的四个小坑

1. 前导零漏判 。"0" 合法、"01" 非法，判断条件是 len(seg) > 1 && seg[0] == '0'。如果写成 seg[0] == '0' 就非法，直接把 0.0.0.0 这个合法解干掉了。重点看 010010 这个用例：0.1.0.010、0.10.01.0 这些组合全部被前导零检查拦下，只输出两个合法结果。
2. 终止条件写成「或」 。只判断 len(path) == 4 不判断字符用完，"25525511" 会误收 2.5.5.2；只判断字符用完不判断段数，凑不够 4 段的也会混进去。
3. 忘了剪枝也能过，但不好 。不加可行性剪枝，代码照样正确，就是会多跑很多无效分支。
4. 用暴力三重循环切 。枚举三个切割点也能做，但回溯写法更通用——把「4 段」换成「k 段」，回溯改一个参数就行，暴力要重构。

3. 复杂度分析

维度	复杂度	说明
时间	O ( 3 4 × ∣ s ∣ ) O(3^4 \times \lvert s \rvert) O(34×∣s∣)	树最多 4 层，每层 3 个分支，叶子节点最多 3 4 = 81 3^4 = 81 34=81 个；每片叶子要 O ( ∣ s ∣ ) O(\lvert s \rvert) O(∣s∣) 拼字符串。段数固定，搜索空间是常数级
空间	O ( ∣ s ∣ ) O(\lvert s \rvert) O(∣s∣)	递归深度不超过 4，路径存储 O ( ∣ s ∣ ) O(\lvert s \rvert) O(∣s∣)，不计结果集

这道题的搜索空间被「恰好 4 段」锁死了，所以时间复杂度其实非常低。但如果把问题泛化成「切成 k 段」，时间复杂度就变成：

T ( k ) = O ( 3 k × ∣ s ∣ ) T(k) = O(3^k \times \lvert s \rvert) T(k)=O(3k×∣s∣)

这时候剪枝的价值就体现出来了——可行性剪枝能在中途就毙掉大量注定无解的分支。

4. 沉淀：回溯模板

IP 题做完，可以把回溯的通用模板提炼出来了。八个字口诀：判终、砍支、循环三连 。

func backtrack(状态) {
    // 1. 判终：到达叶子 → 满足要求则【拷贝快照】收集 → return
    if 到达叶子 {
        if 满足要求 {
            res = append(res, 拷贝(path))
        }
        return
    }
    // 2. 砍支：可行性剪枝，子树必死直接 return
    if 子树必死 {
        return
    }
    // 3. 循环三连：做选择 → 递归 → 还原
    for 选择 := range 选择列表 {
        if 选择非法 { // 合法性剪枝
            continue
        }
        path = append(path, 选择) // 做选择
        backtrack(下一层状态)      // 递归
        path = path[:len(path)-1] // 还原
    }
}

这份模板的每一处细节——「拷贝快照」四个字、「且」不是「或」 ——都对应后文的一次翻车。模板本身十分钟就能背下来，但背下来和会用是两回事。接下来用它在更多题上实战，然后你就看着我怎么翻车的。

4.1 决策三形态

往模板的「选择列表」格子里填东西，只有三种形态：

形态	决策问句	适用条件	代表题
选一个	“从候选里挑哪个？”	这一步必须恰好 做一个选择	排列、组合、映射
要/不要	“这个元素进不进？”	每个元素独立地 可选可不选	子集、01背包
切多长	“下一段切几位？”	序列切割	IP、分割回文串

判断口诀一句话：“这个位置能空着吗？” 能空 → 要/不要；不能空 → 选一个/切一段。

4.2 三验证

决策设计完后，过三个验证才能定稿：

1. 叶子 = 答案？ 每条根到叶路径恰好生成一个完整候选解
2. 无遗漏？ 任何合法答案都存在路径可达（我的错误版在这条上挂掉）
3. 约束局部可判？ 每个决策点上，选择可不可行能用当前状态 O(1) 判断

4.3 同一个骨架的七道题

题目	路径	选择列表	结束条件
复原IP（LC93）	已确定的段	取 1 ∼ 3 1 \sim 3 1∼3 位	4 段且字符用完
全排列（LC46）	已排列的数	未使用的数	排列长度等于 n
括号生成（LC22）	已拼接的串	放 ( 或 )	长度等于 2n
分割回文串（LC131）	已切出的子串	下一段切在哪	切完整个字符串
单词搜索（LC79）	已走的格子	上下左右	匹配完单词
火柴拼正方形（LC473）	各桶当前长度	这根火柴放哪个桶	火柴放完
N 皇后（LC51）	已放的皇后	当前行哪一列	放完 n 行

同一个模板，换汤不换药。理论上把这一道题吃透，等于顺手带走了一批题——但实际上，我马上就在下一道题上翻车了 。

总结

本篇从一道 IP 题走完了回溯的标准建模流程：约束拆解 → 决策树 → 三要素 → 三层剪枝 → 代码实现 → 模板沉淀。带走三样东西：

• 一份模板 ：判终、砍支、循环三连
• 一个决策分类法 ：选一个 / 要不要 / 切多长，口诀是”这个位置能空着吗”
• 一套验证 ：叶子=答案、无遗漏、约束局部可判

模板到手，看起来回溯也就这么回事。下一篇开始，用这个模板在五道题上实战，翻五个坑——决策粒度、切片引用、模型滥用、去重、范式识别——其中一个坑让 24 个排列丢了一半，另一个坑同一考点伏击了我三次。

参考资料

• LeetCode 93. 复原 IP 地址

---

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。