中国wix网站制作公司,wordpress模版怎么弄,做网站优化公司排行,用户登录页面html代码文章目录 一、引言二、回溯算法的核心概念三、组合问题1. LeetCode 77. 组合2. LeetCode 216. 组合总和III3. LeetCode 17. 电话号码的字母组合4. LeetCode 39. 组合总和5. LeetCode 40. 组合总和 II小结 四、分割问题6. LeetCode 131. 分割回文串7. LeetCode 93. 复原IP地址小… 文章目录 一、引言二、回溯算法的核心概念三、组合问题1. LeetCode 77. 组合2. LeetCode 216. 组合总和III3. 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循环控制选择的顺序而排列问题则会基于深度优先搜索实现路径的构建。 回溯算法整体框架流程图 #mermaid-svg-xWlkw7uXpPzSIQyV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-xWlkw7uXpPzSIQyV .error-icon{fill:#552222;}#mermaid-svg-xWlkw7uXpPzSIQyV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-xWlkw7uXpPzSIQyV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-xWlkw7uXpPzSIQyV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-xWlkw7uXpPzSIQyV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-xWlkw7uXpPzSIQyV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-xWlkw7uXpPzSIQyV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-xWlkw7uXpPzSIQyV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-xWlkw7uXpPzSIQyV .marker.cross{stroke:#333333;}#mermaid-svg-xWlkw7uXpPzSIQyV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-xWlkw7uXpPzSIQyV .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-xWlkw7uXpPzSIQyV .cluster-label text{fill:#333;}#mermaid-svg-xWlkw7uXpPzSIQyV .cluster-label span{color:#333;}#mermaid-svg-xWlkw7uXpPzSIQyV .label text,#mermaid-svg-xWlkw7uXpPzSIQyV span{fill:#333;color:#333;}#mermaid-svg-xWlkw7uXpPzSIQyV .node rect,#mermaid-svg-xWlkw7uXpPzSIQyV .node circle,#mermaid-svg-xWlkw7uXpPzSIQyV .node ellipse,#mermaid-svg-xWlkw7uXpPzSIQyV .node polygon,#mermaid-svg-xWlkw7uXpPzSIQyV .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-xWlkw7uXpPzSIQyV .node .label{text-align:center;}#mermaid-svg-xWlkw7uXpPzSIQyV .node.clickable{cursor:pointer;}#mermaid-svg-xWlkw7uXpPzSIQyV .arrowheadPath{fill:#333333;}#mermaid-svg-xWlkw7uXpPzSIQyV .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-xWlkw7uXpPzSIQyV .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-xWlkw7uXpPzSIQyV .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-xWlkw7uXpPzSIQyV .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-xWlkw7uXpPzSIQyV .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-xWlkw7uXpPzSIQyV .cluster text{fill:#333;}#mermaid-svg-xWlkw7uXpPzSIQyV .cluster span{color:#333;}#mermaid-svg-xWlkw7uXpPzSIQyV div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-xWlkw7uXpPzSIQyV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 否 是 否 是 开始 选择元素 是否满足条件? 回溯 记录结果 是否所有元素均尝试? 结束 在接下来的章节中我们将具体分析这15道力扣题目深入解读回溯算法在不同问题场景下的应用与技巧。 三、组合问题
组合问题的特点是每个解都是一个子集或集合且不要求集合中的元素有顺序性。下面是具体题目实现与解析。 1. LeetCode 77. 组合
题目分析 题目要求从1到n中选出k个数字的组合。通过递归逐步构建组合若达到所需长度则收集结果。此题中的路径长度就是终止条件。
组合问题的回溯流程 #mermaid-svg-13GmiSXrQaUi0UED {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-13GmiSXrQaUi0UED .error-icon{fill:#552222;}#mermaid-svg-13GmiSXrQaUi0UED .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-13GmiSXrQaUi0UED .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-13GmiSXrQaUi0UED .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-13GmiSXrQaUi0UED .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-13GmiSXrQaUi0UED .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-13GmiSXrQaUi0UED .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-13GmiSXrQaUi0UED .marker{fill:#333333;stroke:#333333;}#mermaid-svg-13GmiSXrQaUi0UED .marker.cross{stroke:#333333;}#mermaid-svg-13GmiSXrQaUi0UED svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-13GmiSXrQaUi0UED .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-13GmiSXrQaUi0UED .cluster-label text{fill:#333;}#mermaid-svg-13GmiSXrQaUi0UED .cluster-label span{color:#333;}#mermaid-svg-13GmiSXrQaUi0UED .label text,#mermaid-svg-13GmiSXrQaUi0UED span{fill:#333;color:#333;}#mermaid-svg-13GmiSXrQaUi0UED .node rect,#mermaid-svg-13GmiSXrQaUi0UED .node circle,#mermaid-svg-13GmiSXrQaUi0UED .node ellipse,#mermaid-svg-13GmiSXrQaUi0UED .node polygon,#mermaid-svg-13GmiSXrQaUi0UED .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-13GmiSXrQaUi0UED .node .label{text-align:center;}#mermaid-svg-13GmiSXrQaUi0UED .node.clickable{cursor:pointer;}#mermaid-svg-13GmiSXrQaUi0UED .arrowheadPath{fill:#333333;}#mermaid-svg-13GmiSXrQaUi0UED .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-13GmiSXrQaUi0UED .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-13GmiSXrQaUi0UED .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-13GmiSXrQaUi0UED .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-13GmiSXrQaUi0UED .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-13GmiSXrQaUi0UED .cluster text{fill:#333;}#mermaid-svg-13GmiSXrQaUi0UED .cluster span{color:#333;}#mermaid-svg-13GmiSXrQaUi0UED div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-13GmiSXrQaUi0UED :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 是 否 是 否 开始组合生成 选择第一个元素 递归选择下一个元素 达到目标组合长度? 记录组合 回溯,撤销选择 是否有更多元素可选? 结束 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 [][]intvar path []intvar 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 // 撤销选择ipath 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 []stringvar path []bytel : 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 [][]intvar path []intvar sum intvar 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 [][]intvar path []intvar sum intsort.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 l1, r-1 {if s[l] ! s[r] {return false}}return true
}func partition(s string) [][]string {var res [][]stringvar path []stringl : 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 : i1]) { // 判断子串是否为回文continue}path append(path, s[start:i1]) // 选择当前回文子串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 []stringvar path []stringl : len(s)var backTrack func(start int)backTrack func(start int) {// 当path有4段且字符串用完表示找到一个有效IPif 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(start3, l); i {segment : s[start : i1]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 [][]intvar path []intl : 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 sortfunc subsetsWithDup(nums []int) [][]int {var res [][]intvar path []intsort.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 [][]intvar path []intl : 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 sortfunc permuteUnique(nums []int) [][]int {var res [][]intvar path []intl : 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皇后问题的棋盘递归流程 #mermaid-svg-VeGJ94WeBBGkfejq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-VeGJ94WeBBGkfejq .error-icon{fill:#552222;}#mermaid-svg-VeGJ94WeBBGkfejq .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-VeGJ94WeBBGkfejq .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-VeGJ94WeBBGkfejq .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-VeGJ94WeBBGkfejq .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-VeGJ94WeBBGkfejq .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-VeGJ94WeBBGkfejq .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-VeGJ94WeBBGkfejq .marker{fill:#333333;stroke:#333333;}#mermaid-svg-VeGJ94WeBBGkfejq .marker.cross{stroke:#333333;}#mermaid-svg-VeGJ94WeBBGkfejq svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-VeGJ94WeBBGkfejq .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-VeGJ94WeBBGkfejq .cluster-label text{fill:#333;}#mermaid-svg-VeGJ94WeBBGkfejq .cluster-label span{color:#333;}#mermaid-svg-VeGJ94WeBBGkfejq .label text,#mermaid-svg-VeGJ94WeBBGkfejq span{fill:#333;color:#333;}#mermaid-svg-VeGJ94WeBBGkfejq .node rect,#mermaid-svg-VeGJ94WeBBGkfejq .node circle,#mermaid-svg-VeGJ94WeBBGkfejq .node ellipse,#mermaid-svg-VeGJ94WeBBGkfejq .node polygon,#mermaid-svg-VeGJ94WeBBGkfejq .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-VeGJ94WeBBGkfejq .node .label{text-align:center;}#mermaid-svg-VeGJ94WeBBGkfejq .node.clickable{cursor:pointer;}#mermaid-svg-VeGJ94WeBBGkfejq .arrowheadPath{fill:#333333;}#mermaid-svg-VeGJ94WeBBGkfejq .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-VeGJ94WeBBGkfejq .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-VeGJ94WeBBGkfejq .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-VeGJ94WeBBGkfejq .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-VeGJ94WeBBGkfejq .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-VeGJ94WeBBGkfejq .cluster text{fill:#333;}#mermaid-svg-VeGJ94WeBBGkfejq .cluster span{color:#333;}#mermaid-svg-VeGJ94WeBBGkfejq div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-VeGJ94WeBBGkfejq :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 否 是 是 否 开始N皇后 在第1行选择位置 是否符合规则? 递归到下一行 是否完成所有行放置? 记录棋盘解法 回溯撤销选择 Go语言实现
func solveNQueens(n int) [][]string {var res [][]stringboard : 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) boolisValid 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, col1; i 0 j n; i, j i-1, j1 {if board[i][j] Q {return false}}return true}// 将当前棋盘状态转换为字符串形式var formatBoard func() []stringformatBoard func() []string {var result []stringfor _, 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逐一尝试检查当前数字是否符合数独规则若符合则递归填充下一个空白格。填充完成后进行回溯以探索其他可能解。
解数独的回溯流程图 #mermaid-svg-uRr9yaWjNa5yWc9P {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-uRr9yaWjNa5yWc9P .error-icon{fill:#552222;}#mermaid-svg-uRr9yaWjNa5yWc9P .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-uRr9yaWjNa5yWc9P .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-uRr9yaWjNa5yWc9P .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-uRr9yaWjNa5yWc9P .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-uRr9yaWjNa5yWc9P .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-uRr9yaWjNa5yWc9P .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-uRr9yaWjNa5yWc9P .marker{fill:#333333;stroke:#333333;}#mermaid-svg-uRr9yaWjNa5yWc9P .marker.cross{stroke:#333333;}#mermaid-svg-uRr9yaWjNa5yWc9P svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-uRr9yaWjNa5yWc9P .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-uRr9yaWjNa5yWc9P .cluster-label text{fill:#333;}#mermaid-svg-uRr9yaWjNa5yWc9P .cluster-label span{color:#333;}#mermaid-svg-uRr9yaWjNa5yWc9P .label text,#mermaid-svg-uRr9yaWjNa5yWc9P span{fill:#333;color:#333;}#mermaid-svg-uRr9yaWjNa5yWc9P .node rect,#mermaid-svg-uRr9yaWjNa5yWc9P .node circle,#mermaid-svg-uRr9yaWjNa5yWc9P .node ellipse,#mermaid-svg-uRr9yaWjNa5yWc9P .node polygon,#mermaid-svg-uRr9yaWjNa5yWc9P .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-uRr9yaWjNa5yWc9P .node .label{text-align:center;}#mermaid-svg-uRr9yaWjNa5yWc9P .node.clickable{cursor:pointer;}#mermaid-svg-uRr9yaWjNa5yWc9P .arrowheadPath{fill:#333333;}#mermaid-svg-uRr9yaWjNa5yWc9P .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-uRr9yaWjNa5yWc9P .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-uRr9yaWjNa5yWc9P .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-uRr9yaWjNa5yWc9P .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-uRr9yaWjNa5yWc9P .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-uRr9yaWjNa5yWc9P .cluster text{fill:#333;}#mermaid-svg-uRr9yaWjNa5yWc9P .cluster span{color:#333;}#mermaid-svg-uRr9yaWjNa5yWc9P div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-uRr9yaWjNa5yWc9P :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 否 是 是 否 开始解数独 选择空白格 尝试填入1-9 数字是否合法? 递归到下一个空白格 是否全部填充完成? 记录解法 回溯撤销 Go语言实现
func solveSudoku(board [][]byte) {var backTrack func() boolbackTrack func() bool {for i : 0; i 9; i {for j : 0; j 9; j {// 跳过已填充的格子if board[i][j] ! . {continue}// 尝试填充1到9for 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)*3for i : startRow; i startRow3; i {for j : startCol; j startCol3; j {if board[i][j] num {return false}}}return true
}详细解读 终止条件 数独填充完所有空格时返回true表示解数独成功。 结果收集条件 当所有空格均填充有效数字时返回true表示找到解。 去重逻辑 每次填充数字前通过isValidSudoku检查是否有重复确保合法。 递归控制 递归顺序按行列填充若当前格子无合适数字则返回上层重新选择。 小结
棋盘问题的解法在回溯过程中充分利用了位置冲突检测和条件校验
位置合法性检查每次递归前进行条件校验确保放置的元素皇后或数字符合问题规则。递归路径的回溯递归完成后通过回溯撤销选择恢复状态以便尝试新的解法。多层次条件判断棋盘问题的递归逻辑中条件判断多尤其是涉及行、列和对角线或3x3区域的冲突检测。
以上棋盘问题展示了如何在递归过程中处理复杂的棋盘状态和规则检测。接下来我们将继续分析其他复杂问题的解法与实现。 八、其他复杂问
这一类问题虽然不直接涉及棋盘或固定的数组结构但仍可以使用回溯算法通过递归探索不同的路径组合满足特定的条件限制。以下分别是递增子序列和行程重排问题的分析与实现。 14. LeetCode 491. 递增子序列
题目分析 给定一个整数组nums要求找到所有长度大于等于2的递增子序列使得子序列中的元素按原数组中的顺序排列。结果集中不能有重复的子序列。
思路解析 递归生成子序列的每个元素时确保新加入的元素满足递增要求并且通过去重逻辑防止重复子序列的生成。具体来说递归过程中会跳过当前层级的重复元素同时用一个临时哈希表避免在同一层中选取相同的数字。
递增子序列生成的回溯流程图 #mermaid-svg-j7vKPMiER8GmkAZW {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-j7vKPMiER8GmkAZW .error-icon{fill:#552222;}#mermaid-svg-j7vKPMiER8GmkAZW .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-j7vKPMiER8GmkAZW .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-j7vKPMiER8GmkAZW .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-j7vKPMiER8GmkAZW .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-j7vKPMiER8GmkAZW .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-j7vKPMiER8GmkAZW .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-j7vKPMiER8GmkAZW .marker{fill:#333333;stroke:#333333;}#mermaid-svg-j7vKPMiER8GmkAZW .marker.cross{stroke:#333333;}#mermaid-svg-j7vKPMiER8GmkAZW svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-j7vKPMiER8GmkAZW .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-j7vKPMiER8GmkAZW .cluster-label text{fill:#333;}#mermaid-svg-j7vKPMiER8GmkAZW .cluster-label span{color:#333;}#mermaid-svg-j7vKPMiER8GmkAZW .label text,#mermaid-svg-j7vKPMiER8GmkAZW span{fill:#333;color:#333;}#mermaid-svg-j7vKPMiER8GmkAZW .node rect,#mermaid-svg-j7vKPMiER8GmkAZW .node circle,#mermaid-svg-j7vKPMiER8GmkAZW .node ellipse,#mermaid-svg-j7vKPMiER8GmkAZW .node polygon,#mermaid-svg-j7vKPMiER8GmkAZW .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-j7vKPMiER8GmkAZW .node .label{text-align:center;}#mermaid-svg-j7vKPMiER8GmkAZW .node.clickable{cursor:pointer;}#mermaid-svg-j7vKPMiER8GmkAZW .arrowheadPath{fill:#333333;}#mermaid-svg-j7vKPMiER8GmkAZW .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-j7vKPMiER8GmkAZW .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-j7vKPMiER8GmkAZW .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-j7vKPMiER8GmkAZW .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-j7vKPMiER8GmkAZW .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-j7vKPMiER8GmkAZW .cluster text{fill:#333;}#mermaid-svg-j7vKPMiER8GmkAZW .cluster span{color:#333;}#mermaid-svg-j7vKPMiER8GmkAZW div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-j7vKPMiER8GmkAZW :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 否 是 是 否 开始生成递增子序列 选择一个元素加入序列 是否满足递增条件? 跳过,尝试下一个 递归到下一元素 是否到达序列末尾? 记录序列 回溯撤销选择 Go语言实现
func findSubsequences(nums []int) [][]int {var res [][]intvar path []intl : 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开始的行程。
思路解析 先对票据进行字典序排序然后通过回溯找到符合条件的行程路径。递归过程中每次选择一个目的地前往若路径完整即为解。此外在使用票据时需要标记票据是否被使用确保每张票仅用一次。
重新安排行程的递归流程 #mermaid-svg-0vECNyJN6dmCU0bX {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-0vECNyJN6dmCU0bX .error-icon{fill:#552222;}#mermaid-svg-0vECNyJN6dmCU0bX .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-0vECNyJN6dmCU0bX .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-0vECNyJN6dmCU0bX .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-0vECNyJN6dmCU0bX .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-0vECNyJN6dmCU0bX .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-0vECNyJN6dmCU0bX .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-0vECNyJN6dmCU0bX .marker{fill:#333333;stroke:#333333;}#mermaid-svg-0vECNyJN6dmCU0bX .marker.cross{stroke:#333333;}#mermaid-svg-0vECNyJN6dmCU0bX svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-0vECNyJN6dmCU0bX .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-0vECNyJN6dmCU0bX .cluster-label text{fill:#333;}#mermaid-svg-0vECNyJN6dmCU0bX .cluster-label span{color:#333;}#mermaid-svg-0vECNyJN6dmCU0bX .label text,#mermaid-svg-0vECNyJN6dmCU0bX span{fill:#333;color:#333;}#mermaid-svg-0vECNyJN6dmCU0bX .node rect,#mermaid-svg-0vECNyJN6dmCU0bX .node circle,#mermaid-svg-0vECNyJN6dmCU0bX .node ellipse,#mermaid-svg-0vECNyJN6dmCU0bX .node polygon,#mermaid-svg-0vECNyJN6dmCU0bX .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-0vECNyJN6dmCU0bX .node .label{text-align:center;}#mermaid-svg-0vECNyJN6dmCU0bX .node.clickable{cursor:pointer;}#mermaid-svg-0vECNyJN6dmCU0bX .arrowheadPath{fill:#333333;}#mermaid-svg-0vECNyJN6dmCU0bX .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-0vECNyJN6dmCU0bX .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-0vECNyJN6dmCU0bX .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-0vECNyJN6dmCU0bX .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-0vECNyJN6dmCU0bX .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-0vECNyJN6dmCU0bX .cluster text{fill:#333;}#mermaid-svg-0vECNyJN6dmCU0bX .cluster span{color:#333;}#mermaid-svg-0vECNyJN6dmCU0bX div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-0vECNyJN6dmCU0bX :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 是 否 起点:JFK 选择目的地按字典序 递归到下一目的地 是否所有票据使用完毕? 记录行程 回溯,恢复上次选择 Go语言实现
import sortfunc 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上多类问题的应用。回溯算法通过递归与路径回退的组合能够灵活地解决多种组合、分割、子集、排列、棋盘问题以及其他复杂场景的问题。对于每一道题目我们不仅提供了具体的解题思路还重点分析了回溯算法中的关键概念终止条件、路径收集、去重逻辑和递归控制。
通过对每道题目的详细解读本文总结出回溯算法在应对不同题型时的共性和差异性。对于组合和子集问题回溯算法的主要任务是控制元素的选择顺序在排列问题中算法必须关注排列的顺序性在棋盘问题中递归条件更加复杂需要多层次冲突检测而在复杂问题中算法往往需动态地控制路径合法性和顺序。
希望通过这篇文章读者能够更加系统地理解回溯算法在不同问题类型中的应用掌握其在路径选择、条件判断、状态回退等方面的通用模式并能够在遇到类似问题时举一反三设计出高效的回溯解法。
