文章目录
- 一、引言
- 二、回溯算法的核心概念
- 三、组合问题
- 1. LeetCode 77. 组合
- 2. LeetCode 216. 组合总和III
- 3. LeetCode 17. 电话号码的字母组合
- 4. LeetCode 39. 组合总和
- 5. LeetCode 40. 组合总和 II
- 小结
- 四、分割问题
- 6. LeetCode 131. 分割回文串
- 7. LeetCode 93. 复原IP地址
- 小结
- 五、子集问题
- **8. LeetCode 78. 子集**
- 9. LeetCode 90. 子集 II
- 小结
- 六、排列问题
- 10. LeetCode 46. 全排列
- 11. LeetCode 47. 全排列 II
- 小结
- 七、棋盘问题
- 12. LeetCode 51. N皇后
- 13. LeetCode 37. 解数独
- 小结
- 八、其他复杂问
- 14. LeetCode 491. 递增子序列
- 15. LeetCode 332. 重新安排行程
- 小结
- 总结
一、引言
回溯算法是一种利用递归解决搜索问题的常见方法，它在多个编程题型中展现出独特的优势。无论是组合问题、分割问题、子集问题，还是排列、棋盘问题，回溯算法的核心都是在构建路径的同时，动态地选择、撤销操作，最终完成一个全面的搜索。本系列文章将通过15道经典的LeetCode题目，用Go语言实现并深入解析回溯算法的设计模式，帮助您系统化掌握回溯算法在各类问题中的应用。
二、回溯算法的核心概念
在学习回溯算法前，理解其核心概念非常重要。在所有回溯算法的实现中，都离不开以下几个关键部分：
-
递归与回溯的关系：
- 回溯算法是一种基于递归的搜索算法。递归逐层深入，构建一个状态空间树（即递归树），每层递归都代表决策路径的一个选择。
- 一旦递归到达终止条件，回溯将会逐层返回，撤销不符合条件的选择，形成“退一步再试其他路径”的机制。
-
终止条件：
- 每个回溯算法都有一个明确的终止条件，当条件满足时，算法会返回或将结果存储下来。典型的例子包括达成某个组合的长度、和为目标值、或者生成所有排列。
-
结果收集条件：
- 在递归过程中，只有满足条件的路径才会被收集。条件可能是固定的组合大小、具体的和、路径的合法性等。
- 例如在N皇后问题中，结果收集条件是所有皇后均放置完毕且不冲突。
-
去重逻辑：
- 对于一些包含重复元素的问题（如排列或子集问题），去重是关键。常用的去重策略包括提前排序和跳过相同元素。
-
递归控制：
- 循环顺序决定了递归树的遍历路径；递归顺序决定了函数返回的优先顺序。一般来说，组合问题在递归内部通过
for循环控制选择的顺序，而排列问题则会基于深度优先搜索实现路径的构建。
- 循环顺序决定了递归树的遍历路径；递归顺序决定了函数返回的优先顺序。一般来说，组合问题在递归内部通过
-
回溯算法整体框架流程图
在接下来的章节中，我们将具体分析这15道力扣题目，深入解读回溯算法在不同问题场景下的应用与技巧。
三、组合问题
组合问题的特点是每个解都是一个子集或集合，且不要求集合中的元素有顺序性。下面是具体题目实现与解析。
1. LeetCode 77. 组合
题目分析：
题目要求从1到n中选出k个数字的组合。通过递归逐步构建组合，若达到所需长度则收集结果。此题中的路径长度就是终止条件。
组合问题的回溯流程
Go语言实现：
func combine(n int, k int) [][]int {
var res [][]int // 存储最终结果
var path []int // 存储当前组合路径
var backTrack func(s int) // 定义回溯函数
backTrack = func(s int) {
// 当路径长度达到k时，保存当前路径并返回
if len(path) == k {
temp := make([]int, k)
copy(temp, path)
res = append(res, temp)
return
}
// 从s开始选择元素
for i := s; i <= n; i++ {
path = append(path, i) // 选择元素i加入路径
backTrack(i + 1) // 递归调用下一层
path = path[:len(path)-1] // 撤销选择
}
}
backTrack(1) // 从1开始递归
return res
}
详细解读：
- 递归与回溯：
backTrack函数是递归的核心，每次选择后续数字中的一个加入路径。 - 终止条件：当路径长度等于
k时，保存当前路径（组合）。 - 结果收集条件：在路径长度等于
k时，将组合结果收集到res中。 - 去重逻辑：题目不允许重复选择，因此每次递归从
s到n，每层递归仅选择一次。 - 递归控制：循环顺序由
s至n，确保每次递归的元素都是唯一且不重复的。
2. LeetCode 216. 组合总和III
题目分析：
从数字1-9中选出k个数字，使它们的和等于目标值n。在组合过程中需保持路径长度和总和满足条件。
Go语言实现：
func combinationSum(k int, n int) [][]int {
var res [][]int
var path []int
var sum int // 当前路径的总和
var backTrack func(s int)
backTrack = func(s int) {
// 若路径长度和总和同时满足要求，保存结果
if len(path) == k && sum == n {
temp := make([]int, k)
copy(temp, path)
res = append(res, temp)
return
}
// 剪枝条件：路径长度超过k或总和超过n时直接返回
if len(path) > k || sum > n {
return
}
// 从s到9逐一选择元素
for i := s; i <= 9; i++ {
path = append(path, i) // 选择i加入路径
sum += i // 更新路径总和
backTrack(i + 1) // 递归调用下一层
sum -= i // 撤销选择i
path = path[:len(path)-1] // 回溯到上层状态
}
}
backTrack(1)
return res
}
详细解读：
- 终止条件：当路径长度达到
k且总和等于n时，保存组合。 - 结果收集条件：在满足
k和n的条件时，记录路径。 - 去重逻辑：依次递归选取1-9的数字，通过
s递归参数限制重复选择。 - 剪枝条件：提前检查路径长度和总和，避免无效递归。
- 递归控制：使用
s至9的递增顺序，保证路径中无重复数字。
3. LeetCode 17. 电话号码的字母组合
题目分析：
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。每个数字代表一组字母，要求构造出所有可能的字母排列组合。
思路解析：
这道题的关键在于逐层递归处理每个数字对应的字母组合，并在满足条件后将路径保存下来。递归深度等于数字长度，而每层递归中的循环则负责选择不同的字母。通过回溯删除不符合的路径，从而覆盖所有组合。
Go语言实现：
func letterCombinations(digits string) []string {
letters := map[byte][]byte{
'2': {'a', 'b', 'c'},
'3': {'d', 'e', 'f'},
'4': {'g', 'h', 'i'},
'5': {'j', 'k', 'l'},
'6': {'m', 'n', 'o'},
'7': {'p', 'q', 'r', 's'},
'8': {'t', 'u', 'v'},
'9': {'w', 'x', 'y', 'z'},
}
var res []string
var path []byte
l := len(digits)
if l == 0 {
return res
}
var backTrack func(s int)
backTrack = func(s int) {
// 当路径长度达到数字串长度时，将路径转换为字符串并保存
if s == l {
res = append(res, string(path))
return
}
// 选择当前数字对应的每个字母
for _, ch := range letters[digits[s]] {
path = append(path, ch) // 选择一个字母
backTrack(s + 1) // 递归到下一数字
path = path[:len(path)-1] // 撤销选择，回溯到上层状态
}
}
backTrack(0)
return res
}
详细解读：
-
终止条件：
- 当
path长度与digits长度一致时，将当前路径拼接成字符串，并存入结果集。
- 当
-
结果收集条件：
- 在
path长度等于digits时，收集路径。
- 在
-
去重逻辑：
- 每个数字的字母都是固定且不重复的，因此不需要特殊去重处理。
-
递归控制：
- 外层递归控制数字索引；内层循环处理每个数字对应的字母组合。
4. LeetCode 39. 组合总和
题目分析：
从给定的正整数数组candidates中找到所有可能的组合，使得组合中的元素之和等于目标值target。数组中元素可以重复使用。
思路解析：
为保证路径中的数字和达到target且避免重复组合，需要在递归中控制好路径的总和。每层递归会从当前位置到数组结尾进行选择，允许重复选择。若总和超出目标值target，立即停止递归。
Go语言实现：
func combinationSum(candidates []int, target int) [][]int {
var res [][]int
var path []int
var sum int
var backTrack func(s int)
backTrack = func(s int) {
// 当总和超出目标时，停止递归
if sum > target {
return
}
// 当总和达到目标时，记录当前路径
if sum == target {
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
// 从s到数组末尾尝试每个候选数
for i := s; i < len(candidates); i++ {
path = append(path, candidates[i]) // 选择候选数
sum += candidates[i] // 更新路径总和
backTrack(i) // 递归允许重复选择
sum -= candidates[i] // 回溯到上层
path = path[:len(path)-1] // 撤销选择
}
}
backTrack(0)
return res
}
详细解读：
-
终止条件：
- 总和等于目标
target时，将路径存入结果集； - 若总和超过
target，则提前返回，避免无效递归。
- 总和等于目标
-
结果收集条件：
- 在
sum == target时，保存路径。
- 在
-
去重逻辑：
- 候选元素位置递增，无需额外去重。
-
递归控制：
- 每层递归从
s开始，允许同元素在递归中多次选择，形成重复组合的路径。
- 每层递归从
5. LeetCode 40. 组合总和 II
题目分析：
本题和上一题类似，但要求组合中的每个数字只能使用一次，并且不能有重复组合。即在数组中选取不同组合使其和为target，每个组合内部元素可以重复，但组合间不能有重复。
思路解析：
通过提前对数组排序以及递归中的剪枝处理来去重，从而确保不会重复选择同一个元素。每层递归的选择会跳过重复元素，避免组合重复。
Go语言实现：
func combinationSum2(candidates []int, target int) [][]int {
var res [][]int
var path []int
var sum int
sort.Ints(candidates) // 预排序以方便去重
var backTrack func(s int)
backTrack = func(s int) {
if sum == target {
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
if sum > target {
return
}
for i := s; i < len(candidates); i++ {
// 去重：若当前数等于上一个，且在同一层递归中未被选过，则跳过
if i > s && candidates[i] == candidates[i-1] {
continue
}
path = append(path, candidates[i]) // 选择候选数
sum += candidates[i] // 更新路径总和
backTrack(i + 1) // 从下一个元素递归
sum -= candidates[i] // 回溯到上层
path = path[:len(path)-1] // 撤销选择
}
}
backTrack(0)
return res
}
详细解读：
-
终止条件：
- 当
sum等于target时，将路径加入结果集； - 当
sum超过target时，提前返回，停止当前递归。
- 当
-
结果收集条件：
- 在
sum == target时，保存路径。
- 在
-
去重逻辑：
- 排序后在循环中跳过重复元素
candidates[i] == candidates[i-1]，保证每个组合的唯一性。
- 排序后在循环中跳过重复元素
-
递归控制：
- 每层递归选择当前或后续元素，确保每个数只能选一次并避免重复组合。
小结
在组合问题中，回溯算法的核心在于控制组合生成的方式和路径。结合剪枝、去重等方法，不仅能提高算法效率，还能避免重复组合的生成。在实现上，终止条件和结果收集条件的正确设置十分关键。此外，通过for循环控制递归深度和选择范围，能够生成符合题目要求的组合解。
四、分割问题
分割问题的核心在于将给定的字符串分解成多个满足条件的部分。通过回溯逐层递归地探索各个可能的分割点，确保每一层递归选择的部分满足题目要求。以下是具体题目的解析与实现。
6. LeetCode 131. 分割回文串
题目分析：
给定一个字符串s，要求将其分割，使每个分割后的子串都是回文串。返回所有可能的回文分割方案。
思路解析：
该题目需要使用回溯和分治的思想，逐层递归探索字符串的每一个分割位置。对于每一个可能的分割点，检查其是否是回文串，如果是，则继续递归剩下的部分；否则跳过。
Go语言实现：
// 辅助函数：检查是否为回文串
func isPalindrome(s string) bool {
for l, r := 0, len(s)-1; l < r; l, r = l+1, r-1 {
if s[l] != s[r] {
return false
}
}
return true
}
func partition(s string) [][]string {
var res [][]string
var path []string
l := len(s)
var backTrack func(start int)
backTrack = func(start int) {
// 终止条件：到达字符串末尾时，记录当前分割路径
if start == l {
temp := make([]string, len(path))
copy(temp, path)
res = append(res, temp)
return
}
// 从start位置开始尝试分割每个可能的子串
for i := start; i < l; i++ {
if !isPalindrome(s[start : i+1]) { // 判断子串是否为回文
continue
}
path = append(path, s[start:i+1]) // 选择当前回文子串
backTrack(i + 1) // 递归处理剩余部分
path = path[:len(path)-1] // 撤销选择，回溯到上层
}
}
backTrack(0)
return res
}
详细解读：
-
终止条件：
- 当遍历到字符串的末尾时（
start == l），将当前路径path存入结果集中。
- 当遍历到字符串的末尾时（
-
结果收集条件：
- 若当前分割路径到达字符串末尾，将其存入结果集。
-
去重逻辑：
- 本题不存在重复组合的问题，因为每次选择都基于字符串的索引位置，保证了结果的唯一性。
-
递归控制：
- 通过
for循环控制每一层的分割起始位置，逐层向后分割，确保各个分割部分为回文串。
- 通过
7. LeetCode 93. 复原IP地址
题目分析：
给定一个只含数字的字符串，要求将其复原成可能的有效IP地址。IP地址由四个十进制部分组成，每部分在0到255之间，且不能包含前导零。
思路解析：
该题目使用回溯尝试将字符串分割为4部分，每部分代表IP地址的一个段。需要特别注意的是，IP地址每部分的范围限定为0-255，且不能有前导零。递归过程中，当达到4段且字符串用完即为有效分割。
Go语言实现：
import "strconv"
// 辅助函数：检查是否为有效IP地址段
func isValidSegment(s string) bool {
if len(s) == 0 || (len(s) > 1 && s[0] == '0') {
return false
}
num, _ := strconv.Atoi(s)
return num >= 0 && num <= 255
}
func restoreIpAddresses(s string) []string {
var res []string
var path []string
l := len(s)
var backTrack func(start int)
backTrack = func(start int) {
// 当path有4段且字符串用完，表示找到一个有效IP
if len(path) == 4 && start == l {
res = append(res, path[0]+"."+path[1]+"."+path[2]+"."+path[3])
return
}
// 若path已达4段但未用完字符串，提前结束
if len(path) == 4 {
return
}
// 遍历每个可能的分割点，每段最多3位
for i := start; i < min(start+3, l); i++ {
segment := s[start : i+1]
if !isValidSegment(segment) {
continue
}
path = append(path, segment) // 选择有效IP段
backTrack(i + 1) // 递归处理剩余字符串
path = path[:len(path)-1] // 回溯，撤销选择
}
}
backTrack(0)
return res
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
详细解读：
-
终止条件：
- 当
path长度等于4段且字符串用完时，表示找到一个有效的IP地址，将其存入结果集。 - 若
path已达4段，但未用完字符串，则提前结束当前路径。
- 当
-
结果收集条件：
- 在满足4段IP和完整字符串条件时，将路径加入结果集。
-
去重逻辑：
- 本题不存在重复组合，因为每段分割仅对应一个合法的IP段。
-
递归控制：
- 递归逐层分割，每层递归最多选择3个字符作为IP地址段，避免超过有效长度。
小结
分割问题的回溯算法设计关键在于：
- 分割点的选择与递归控制：每一层递归都尝试不同的分割点，以探索多种可能的路径。
- 有效性校验：分割后的子串必须符合特定条件（如回文或IP段的范围），在递归选择时及时进行校验，避免无效路径。
- 路径收集条件：只有满足条件的路径（如达到分割段数）才会收集到最终结果集中。
五、子集问题
子集问题需要在给定数组中找到所有可能的子集组合。这里的关键是每个元素的选择与不选择，形成不同的组合方案。子集问题的核心思路是通过递归回溯，逐步生成所有可能的子集组合。
8. LeetCode 78. 子集
题目分析：
给定一个不含重复元素的整数数组nums，求所有的子集（包括空集）。该题要求返回所有可能的子集，因此每个元素都有加入和不加入当前组合的两种选择。
思路解析：
通过递归遍历数组，分别处理每个元素的“加入”和“不加入”操作，逐步构建出所有的子集。由于子集中没有顺序要求，递归中可以按顺序加入新元素，不必考虑排列顺序。
Go语言实现：
func subsets(nums []int) [][]int {
var res [][]int
var path []int
l := len(nums)
var backTrack func(start int)
backTrack = func(start int) {
// 将当前路径加入结果集中
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
// 从当前元素开始，递归构建子集
for i := start; i < l; i++ {
path = append(path, nums[i]) // 选择当前元素
backTrack(i + 1) // 递归生成后续子集
path = path[:len(path)-1] // 撤销选择，回溯
}
}
backTrack(0)
return res
}
详细解读：
-
终止条件：
- 每次递归调用都会将当前路径加入结果集，无需特定终止条件。
-
结果收集条件：
- 在每层递归中将路径
path加入res，表示当前组合就是一个子集。
- 在每层递归中将路径
-
去重逻辑：
- 因为数组不包含重复元素，每次递归中不需要去重操作。
-
递归控制：
- 每层递归的
for循环从当前位置开始，确保每个组合无重复顺序，形成不同的子集。
- 每层递归的
9. LeetCode 90. 子集 II
题目分析：
与上一题不同的是，给定的数组nums中包含重复元素，求所有可能的子集。由于存在重复元素，需要确保相同的元素不会生成重复的子集。
思路解析：
为避免重复组合，首先对数组进行排序，这样在递归过程中可以跳过重复的元素。若当前元素与前一个元素相同，且前一个元素未被选择，则跳过当前元素，确保唯一性。
Go语言实现：
import "sort"
func subsetsWithDup(nums []int) [][]int {
var res [][]int
var path []int
sort.Ints(nums) // 预排序以便去重
var backTrack func(start int)
backTrack = func(start int) {
// 保存当前路径作为子集
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
// 从start位置开始递归
for i := start; i < len(nums); i++ {
// 去重：若当前元素等于上一个且未被选过，则跳过
if i > start && nums[i] == nums[i-1] {
continue
}
path = append(path, nums[i]) // 选择当前元素
backTrack(i + 1) // 递归到下一个位置
path = path[:len(path)-1] // 回溯，撤销选择
}
}
backTrack(0)
return res
}
详细解读：
-
终止条件：
- 每次递归调用都会将当前路径加入结果集，形成一个子集。
-
结果收集条件：
- 在每层递归中将当前路径
path加入res，即收集当前形成的子集。
- 在每层递归中将当前路径
-
去重逻辑：
- 数组排序后，利用条件
if i > start && nums[i] == nums[i-1]跳过重复的元素，防止生成重复子集。
- 数组排序后，利用条件
-
递归控制：
- 每层递归的
for循环从start位置开始，以保证子集生成的顺序不变且不重复。
- 每层递归的
小结
子集问题通过递归生成所有组合，关键在于：
- 选择与不选择的决策：每个元素都面临“加入”或“不加入”的选择，这构成了回溯递归的基本框架。
- 去重逻辑的实现：在含重复元素的子集问题中，提前排序并在递归过程中跳过相同元素，确保生成的子集组合唯一。
- 路径收集的时机：每个递归点的路径即为一个子集，因此在每次递归时都保存当前路径。
通过对比78和90两道题，可以看到在处理重复元素和去重逻辑上的不同应用。接下来我们将进入排列问题的分析与实现。
六、排列问题
排列问题要求对给定数组生成所有可能的排列，特别是每个排列中元素的顺序必须唯一。排列问题的核心思路是使用递归回溯，从给定数组逐个选择元素加入路径，直到路径长度等于数组长度时生成一个排列。
10. LeetCode 46. 全排列
题目分析：
给定一个不含重复数字的数组nums，要求返回其所有可能的排列。该题与组合和子集问题的区别在于，排列中的顺序不同会产生不同的排列结果，因此递归过程中需要处理元素的交换和位置选择。
思路解析：
使用回溯法，在每层递归中按顺序选择一个未使用的元素加入路径，直到路径长度与数组长度一致。每次递归结束后回退选择，恢复现场，确保所有位置都被遍历到。
Go语言实现：
func permute(nums []int) [][]int {
var res [][]int
var path []int
l := len(nums)
used := make(map[int]bool) // 记录每个元素是否已在当前排列中使用
var backTrack func()
backTrack = func() {
// 当路径长度等于数组长度时，保存当前排列
if len(path) == l {
temp := make([]int, l)
copy(temp, path)
res = append(res, temp)
return
}
// 遍历每个元素
for i := 0; i < l; i++ {
if used[nums[i]] {
continue // 跳过已使用的元素
}
used[nums[i]] = true // 标记元素已使用
path = append(path, nums[i]) // 选择当前元素
backTrack() // 递归生成后续排列
path = path[:len(path)-1] // 撤销选择，回溯
used[nums[i]] = false // 取消标记
}
}
backTrack()
return res
}
详细解读：
-
终止条件：
- 当路径长度等于数组长度时，表示形成了一个完整的排列，加入结果集。
-
结果收集条件：
- 在递归层次达到数组长度时，将当前路径
path加入结果集。
- 在递归层次达到数组长度时，将当前路径
-
去重逻辑：
- 每次递归中使用
used字典标记每个元素是否已在当前排列路径中，避免重复选择。
- 每次递归中使用
-
递归控制：
for循环遍历数组中每一个元素，并在递归中控制元素选择与撤销，从而生成所有排列。
11. LeetCode 47. 全排列 II
题目分析：
与前一题不同的是，给定的数组nums中可能包含重复元素，要求生成的排列中不应有重复项。因此在递归中需要确保相同的元素不会导致重复排列。
思路解析：
先对数组排序，这样在递归时可以通过判断跳过相同元素以去重。此外，若前一个相同的元素未被选过，则当前元素也不能选，确保每层递归中生成的排列唯一。
Go语言实现：
import "sort"
func permuteUnique(nums []int) [][]int {
var res [][]int
var path []int
l := len(nums)
used := make([]bool, l) // 记录每个位置的元素是否已被选中
sort.Ints(nums) // 排序以便去重
var backTrack func()
backTrack = func() {
// 当路径长度等于数组长度时，保存当前排列
if len(path) == l {
temp := make([]int, l)
copy(temp, path)
res = append(res, temp)
return
}
// 遍历每个元素
for i := 0; i < l; i++ {
// 去重逻辑：跳过重复元素
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue
}
if used[i] {
continue
}
used[i] = true // 标记元素已使用
path = append(path, nums[i]) // 选择当前元素
backTrack() // 递归生成后续排列
path = path[:len(path)-1] // 撤销选择，回溯
used[i] = false // 取消标记
}
}
backTrack()
return res
}
详细解读：
-
终止条件：
- 路径长度等于数组长度时，生成一个完整排列，加入结果集。
-
结果收集条件：
- 在递归层次等于数组长度时，将当前排列路径
path加入res。
- 在递归层次等于数组长度时，将当前排列路径
-
去重逻辑：
- 排序后，跳过已选过的相同元素（
nums[i] == nums[i-1] && !used[i-1]），避免重复排列的生成，去重操作仅作用于当前递归层。
- 排序后，跳过已选过的相同元素（
-
递归控制：
for循环控制排列的顺序，used数组记录每个元素的使用状态，并在递归和回溯中交替使用。
小结
在排列问题中，通过逐层递归生成所有可能的排列，递归过程中确保唯一性至关重要：
- 路径收集条件：递归深度等于数组长度时表示一个完整的排列，及时收集。
- 去重策略的应用：排序和跳过相同元素的逻辑可有效去除重复排列。
- 递归结构：每层递归中控制元素的选择、加入、撤销，通过递归的深度优先遍历实现所有排列的组合。
在比较46和47题时可以看到，包含重复元素的排列需要在递归中加入去重策略，确保排列唯一性。接下来将进入棋盘问题的解析与实现。
七、棋盘问题
棋盘问题通常涉及在棋盘上放置棋子（如皇后或数字），满足特定规则。回溯算法在棋盘问题中广泛应用，因为回溯能够有效地处理棋子的放置、撤回以及合法性检测，从而找到所有可能的棋盘解法。
12. LeetCode 51. N皇后
题目分析：
在n x n的棋盘上放置n个皇后，使得任意两个皇后都不在同一行、同一列或同一条对角线上。要求返回所有可能的放置方案。
思路解析：
该题可以通过回溯解决，每次递归在棋盘的某一行放置皇后，然后递归到下一行，检查每个位置是否会与已放置的皇后冲突。若冲突则跳过该位置，若无冲突则放置皇后并继续递归。递归完成后通过回溯撤销选择，以便探索下一种可能方案。
N皇后问题的棋盘递归流程
Go语言实现：
func solveNQueens(n int) [][]string {
var res [][]string
board := make([][]string, n) // 创建棋盘
for i := range board {
board[i] = make([]string, n)
for j := range board[i] {
board[i][j] = "." // 初始化棋盘为空位
}
}
// 检查当前放置是否会与已有皇后冲突
var isValid func(row, col int) bool
isValid = func(row, col int) bool {
// 检查列是否有皇后
for i := 0; i < row; i++ {
if board[i][col] == "Q" {
return false
}
}
// 检查左上对角线是否有皇后
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if board[i][j] == "Q" {
return false
}
}
// 检查右上对角线是否有皇后
for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
if board[i][j] == "Q" {
return false
}
}
return true
}
// 将当前棋盘状态转换为字符串形式
var formatBoard func() []string
formatBoard = func() []string {
var result []string
for _, row := range board {
result = append(result, strings.Join(row, ""))
}
return result
}
// 回溯函数
var backTrack func(row int)
backTrack = func(row int) {
if row == n {
res = append(res, formatBoard()) // 所有行已放置完成，记录当前棋盘
return
}
for col := 0; col < n; col++ {
if !isValid(row, col) {
continue
}
board[row][col] = "Q" // 放置皇后
backTrack(row + 1) // 递归到下一行
board[row][col] = "." // 回溯，撤销放置
}
}
backTrack(0) // 从第0行开始递归
return res
}
详细解读：
-
终止条件：
- 当所有行都放置皇后后（即
row == n），将当前棋盘状态加入结果集。
- 当所有行都放置皇后后（即
-
结果收集条件：
- 在放置完所有行的皇后后，将当前棋盘状态
board转换为字符串格式，并存入res。
- 在放置完所有行的皇后后，将当前棋盘状态
-
去重逻辑：
- 不存在重复，因为每次递归基于当前棋盘状态进行放置，确保唯一性。
-
递归控制：
- 每行递归尝试所有列的放置，通过
isValid函数判断是否冲突，递归完成后回溯撤销放置。
- 每行递归尝试所有列的放置，通过
13. LeetCode 37. 解数独
题目分析：
给定一个部分填充的9x9数独，要求填充空白位置，使得每行、每列和每个3x3子区域均包含1到9的数字。数独谜题要求唯一解，因此需要在递归中保证填充的数字唯一合法。
思路解析：
通过回溯逐个填充每一个空白位置，每个位置从1到9逐一尝试，检查当前数字是否符合数独规则，若符合则递归填充下一个空白格。填充完成后进行回溯，以探索其他可能解。
解数独的回溯流程图
Go语言实现：
func solveSudoku(board [][]byte) {
var backTrack func() bool
backTrack = func() bool {
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
// 跳过已填充的格子
if board[i][j] != '.' {
continue
}
// 尝试填充1到9
for k := '1'; k <= '9'; k++ {
if isValidSudoku(board, i, j, byte(k)) {
board[i][j] = byte(k) // 填充数字
if backTrack() { // 递归处理下一空格
return true
}
board[i][j] = '.' // 回溯，撤销填充
}
}
return false // 若无合适数字则返回，回溯上层
}
}
return true // 全部填充完成，返回true
}
backTrack()
}
// 检查填充是否符合数独规则
func isValidSudoku(board [][]byte, row, col int, num byte) bool {
for i := 0; i < 9; i++ {
// 检查行和列是否有相同数字
if board[row][i] == num || board[i][col] == num {
return false
}
}
// 检查3x3子区域是否有相同数字
startRow, startCol := (row/3)*3, (col/3)*3
for i := startRow; i < startRow+3; i++ {
for j := startCol; j < startCol+3; j++ {
if board[i][j] == num {
return false
}
}
}
return true
}
详细解读：
-
终止条件：
- 数独填充完所有空格时返回
true，表示解数独成功。
- 数独填充完所有空格时返回
-
结果收集条件：
- 当所有空格均填充有效数字时，返回
true表示找到解。
- 当所有空格均填充有效数字时，返回
-
去重逻辑：
- 每次填充数字前通过
isValidSudoku检查是否有重复，确保合法。
- 每次填充数字前通过
-
递归控制：
- 递归顺序按行列填充，若当前格子无合适数字，则返回上层重新选择。
小结
棋盘问题的解法在回溯过程中充分利用了位置冲突检测和条件校验：
- 位置合法性检查：每次递归前进行条件校验，确保放置的元素（皇后或数字）符合问题规则。
- 递归路径的回溯：递归完成后通过回溯撤销选择，恢复状态以便尝试新的解法。
- 多层次条件判断：棋盘问题的递归逻辑中条件判断多，尤其是涉及行、列和对角线或3x3区域的冲突检测。
以上棋盘问题展示了如何在递归过程中处理复杂的棋盘状态和规则检测。接下来我们将继续分析其他复杂问题的解法与实现。
八、其他复杂问
这一类问题虽然不直接涉及棋盘或固定的数组结构，但仍可以使用回溯算法，通过递归探索不同的路径组合，满足特定的条件限制。以下分别是递增子序列和行程重排问题的分析与实现。
14. LeetCode 491. 递增子序列
题目分析：
给定一个整数组nums，要求找到所有长度大于等于2的递增子序列，使得子序列中的元素按原数组中的顺序排列。结果集中不能有重复的子序列。
思路解析：
递归生成子序列的每个元素时，确保新加入的元素满足递增要求，并且通过去重逻辑防止重复子序列的生成。具体来说，递归过程中会跳过当前层级的重复元素，同时用一个临时哈希表避免在同一层中选取相同的数字。
递增子序列生成的回溯流程图
Go语言实现：
func findSubsequences(nums []int) [][]int {
var res [][]int
var path []int
l := len(nums)
var backTrack func(start int)
backTrack = func(start int) {
if len(path) >= 2 { // 只记录长度大于等于2的递增子序列
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
}
used := make(map[int]bool) // 当前层级去重
for i := start; i < l; i++ {
// 检查递增性及去重条件
if (len(path) > 0 && nums[i] < path[len(path)-1]) || used[nums[i]] {
continue
}
used[nums[i]] = true // 标记当前元素已使用
path = append(path, nums[i]) // 选择当前元素
backTrack(i + 1) // 递归到下一个位置
path = path[:len(path)-1] // 撤销选择，回溯
}
}
backTrack(0)
return res
}
详细解读：
-
终止条件：
- 没有固定终止条件，每次递归的路径
path长度满足>=2时将路径加入结果集。
- 没有固定终止条件，每次递归的路径
-
结果收集条件：
- 每次递归进入时判断路径长度，若大于等于2则将路径加入结果。
-
去重逻辑：
- 每一层递归中使用
used哈希表记录当前层已选元素，避免重复选择。
- 每一层递归中使用
-
递增性校验：
- 仅当当前元素大于等于路径末尾元素时才加入路径，确保子序列递增。
15. LeetCode 332. 重新安排行程
题目分析：
给定一组行程票据，每张票据表示从某个机场出发，前往另一个机场。要求使用所有票据，按字典序返回从起点JFK开始的行程。
思路解析：
先对票据进行字典序排序，然后通过回溯找到符合条件的行程路径。递归过程中每次选择一个目的地前往，若路径完整即为解。此外，在使用票据时需要标记票据是否被使用，确保每张票仅用一次。
重新安排行程的递归流程
Go语言实现：
import "sort"
func findItinerary(tickets [][]string) []string {
var res []string
// 构建邻接表，按字典序排序每个出发地的目的地
flights := make(map[string][]string)
for _, ticket := range tickets {
from, to := ticket[0], ticket[1]
flights[from] = append(flights[from], to)
}
for from := range flights {
sort.Strings(flights[from])
}
// 回溯函数
var backTrack func(airport string)
backTrack = func(airport string) {
for len(flights[airport]) > 0 {
// 每次选择当前机场的第一个目的地，确保字典序
next := flights[airport][0]
flights[airport] = flights[airport][1:] // 从邻接表中移除已使用票
backTrack(next) // 递归到下一目的地
}
res = append([]string{airport}, res...) // 将当前机场插入到行程的开头
}
backTrack("JFK")
return res
}
详细解读：
-
终止条件：
- 在所有票据用完时终止递归。路径构建完成后将递归路径
res返回。
- 在所有票据用完时终止递归。路径构建完成后将递归路径
-
结果收集条件：
- 每次递归回溯时将当前机场插入到行程路径
res开头，形成最终的行程顺序。
- 每次递归回溯时将当前机场插入到行程路径
-
去重逻辑：
- 每次递归选择时，使用并移除当前目的地，避免重复使用票据。
-
字典序控制：
- 对每个出发地的目的地进行字典序排序，确保按字典序优先构建路径。
小结
在这一类复杂问题中，回溯算法需要更多的条件判断和路径控制来满足题目要求：
- 路径的唯一性和有效性：借助条件判断和状态记录，确保路径符合题目要求。
- 字典序或顺序控制：对于顺序敏感的问题，通过预排序或字典序遍历确保路径符合要求。
- 递归回溯与去重策略：有效的去重方法可以减少重复计算，尤其是在路径中存在重复元素时。
本章通过递增子序列和行程安排问题展示了回溯算法在复杂条件控制中的强大灵活性。
总结
在本文中，我们详细探讨了回溯算法在LeetCode上多类问题的应用。回溯算法通过递归与路径回退的组合，能够灵活地解决多种组合、分割、子集、排列、棋盘问题以及其他复杂场景的问题。对于每一道题目，我们不仅提供了具体的解题思路，还重点分析了回溯算法中的关键概念：终止条件、路径收集、去重逻辑和递归控制。
通过对每道题目的详细解读，本文总结出回溯算法在应对不同题型时的共性和差异性。对于组合和子集问题，回溯算法的主要任务是控制元素的选择顺序；在排列问题中，算法必须关注排列的顺序性；在棋盘问题中，递归条件更加复杂，需要多层次冲突检测；而在复杂问题中，算法往往需动态地控制路径合法性和顺序。
希望通过这篇文章，读者能够更加系统地理解回溯算法在不同问题类型中的应用，掌握其在路径选择、条件判断、状态回退等方面的通用模式，并能够在遇到类似问题时举一反三，设计出高效的回溯解法。
