LeetCode-Go 题解 | 491. Non-decreasing SubsequencesDFS 回溯与双重 Map 去重求解非递减子序列【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于开源仓库 LeetCode-Go 中 491. Non-decreasing Subsequences 题解文档 展开围绕 LeetCode 第 491 题「非递减子序列」的完整解题链路进行讲解从题目约束分析、DFS 回溯算法设计到源码中两层 Map 各自承担的去重职责最后结合仓库内测试用例验证结果。读完本文你将掌握在不可排序必须保留原始相对顺序的前提下如何用 DFS 哈希去重高效枚举所有长度 ≥ 2 的非递减子序列并能将该模板迁移到第 78 题、第 90 题等子序列类问题中。题目描述给定一个整型数组你的任务是找到该数组的所有不同的递增子序列且递增子序列的长度至少为 2。示例Input: [4, 6, 7, 7] Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]注意给定数组的长度不会超过 15数组中的整数范围是 [-100, 100]给定数组中可能包含重复数字相等的数字应被视为递增的一种特殊情况即允许非严格递增。这里的关键点在于本题不要求最终结果按字典序或任何特定顺序输出但要求所有子序列必须是互不相同的集合去重且元素顺序必须与原数组中的相对下标顺序一致。解题思路概述本题思路在 题解文档 中给出明确指引它与第 78 题Subsets和第 90 题Subsets II是同一类问题。第 78、90 题求的是所有子序列本题在此基础上额外增加了两个约束非递减要求子序列内部满足nums[i] nums[j]i j即允许相等长度限制最终只输出长度 ≥ 2 的子序列。需要注意的两个难点原数组元素可能重复直接 DFS 会产出大量重复解最终输出必须去重不能先排序再搜索——因为子序列必须保持原数组的相对顺序排序会破坏下标顺序这正是它与第 90 题在去重策略上的本质差异详见后文对比章节。仓库给出的解法采用DFS 深度优先搜索 Map 去重最终结果输出的去重用外层 Map 处理过滤每组解因重复起始元素导致的重复解数组中重复元素导致的重复用 DFS 遍历搜索时每层的 Map 处理保证本轮 DFS 内不出现重复元素但递归到下一层仍可以选择值相同、下标不同的另一个元素。源码实现逐段解析仓库中的核心实现在 491. Non-decreasing Subsequences.go共包含两个函数入口函数findSubsequences与递归函数generateIncSubsets。入口函数外层循环 起始元素去重func findSubsequences(nums []int) [][]int { c, visited, res : []int{}, map[int]bool{}, [][]int{} for i : 0; i len(nums)-1; i { if _, ok : visited[nums[i]]; ok { continue } else { visited[nums[i]] true generateIncSubsets(nums, i, c, res) } } return res }入口函数负责枚举每个可能的起始下标并维护一个全局visitedMap 记录“已经作为过起始值的元素值”外层循环从0遍历到len(nums)-2因为子序列长度至少为 2最后一个元素不可能作为起点这是一个边界优化当发现nums[i]已经作为起始值被处理过visited[nums[i]]为 true直接continue跳过否则记录该值并以其为起点调用递归函数。这个外层visited的作用正是文档中所述的“过滤每组解因为重复元素导致的重复解”例如输入[4, 6, 7, 7]两个下标不同的 7 作为起点时会各自生成一组以 7 开头的子序列但两组解在内容上完全相同外层 Map 保证同一值只被当作起点一次从而避免整组重复解。递归函数非递减约束 层内去重func generateIncSubsets(nums []int, current int, c []int, res *[][]int) { c append(c, nums[current]) if len(c) 2 { b : make([]int, len(c)) copy(b, c) *res append(*res, b) } visited : map[int]bool{} for i : current 1; i len(nums); i { if nums[current] nums[i] { if _, ok : visited[nums[i]]; ok { continue } else { visited[nums[i]] true generateIncSubsets(nums, i, c, res) } } } c c[:len(c)-1] return }递归函数的四个关键点加入当前元素c append(c, nums[current])将当前下标对应的值追加到路径中收集结果只要当前路径长度 ≥ 2就深拷贝一份makecopy存入res。注意这里使用深拷贝非常关键——因为c是复用的切片后续递归会修改它若不拷贝最终保存的将是同一块底层数组非递减剪枝if nums[current] nums[i]保证只向值不小于当前元素的后续元素递归从而天然满足非递减含相等约束层内去重每一层递归新建一个局部visitedMap记录本轮已经选择过的元素值。与入口函数不同这个 Map 是每层独立的它只禁止本轮 for 循环内选择重复的值但不影响更深层递归去选择“值相同、下标不同”的元素。这正是文档强调的“递归到下一层还可以选择值相同但是下标不同的另外一个元素”。递归返回前执行c c[:len(c)-1]回溯撤销本层选择恢复切片长度。双重 Map 去重原理剖析这是本题最容易混淆的地方值得单独展开。代码中出现了两个visitedMap职责完全不同Map 位置生命周期去重对象具体效果findSubsequences中的visited整个函数共用子序列的起始值值相同的元素只作为起点进入 DFS 一次过滤整组重复解generateIncSubsets中的visited每次递归调用独立当前层 for 循环选择的元素值同一层内不选重复值但更深层仍可选相同值的其他下标以输入[4, 6, 7, 7]为例外层 Map第二个 7 作为起点时被跳过不会重复生成[7]起始的所有子序列层内 Map第一个 7 进入递归后本层 for 循环遇到第二个 7值相同会跳过直接递归避免在同一层重复选择但是递归进入下一层current指向第二个 7后仍然可以继续向后扩展从而产生[7, 7]这类结果。两个 Map 一个管“起点不重复”、一个管“同层选择不重复”配合起来既完整保留了所有合法的非递减子序列又不会输出任何重复解。正确性验证测试用例与预期输出仓库配套的 491. Non-decreasing Subsequences_test.go 通过表驱动方式给出了三组测试用例输入期望输出[4, 3, 2, 1][][4, 6, 7, 7][[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7, 7], [4, 7, 7]][1, 1, 2][[1, 1], [1, 2], [1, 1, 2], [2, 2]]第一组[4, 3, 2, 1]为严格递减数组任意两个元素都不满足非递减条件因此不存在长度 ≥ 2 的子序列输出空集与实现逻辑一致第二组[4, 6, 7, 7]验证了含重复元素且包含非严格递增[7, 7]、[6, 7, 7]、[4, 7, 7]场景下去重与完整枚举都正确第三组[1, 1, 2]用于验证重复起始元素的去重。从源码实现可以推断以第二个 1 为起点生成的子序列内容与第一个 1 完全重复会被外层visited过滤因此实际运行该实现得到的输出应为[[1, 1], [1, 2], [1, 1, 2]]。此处需要特别说明测试文件中期望输出里的[2, 2]与输入[1, 1, 2]仅含一个 2矛盾按当前实现与输入数据推断应为笔误读者在本地运行时可留意该差异。测试文件采用仓库统一的question491/para491/ans491结构组织用例其中para491描述输入、ans491描述期望答案最后通过findSubsequences(p.one)打印实际输出可直观与期望对比。与第 78 / 90 题的横向对比文档明确指出本题与第 78、90 题“可以一起解答和复习”三者对比有助于建立完整的子序列问题知识图谱题目输入特点是否可先排序去重手段输出约束78. Subsets实现无重复无所谓无需去重全部子集含空集90. Subsets II实现有重复可以先sort.Ints(nums)再通过if i start nums[i] nums[i-1]跳过相邻重复排序后按“同层相邻相等则跳过”全部子集含空集491. Non-decreasing Subsequences实现有重复不可以排序会破坏下标相对顺序双 Map外层管起点、层内管同层选择仅长度 ≥ 2 的非递减子序列第 90 题之所以能依赖“排序 相邻相等跳过”去重是因为它不要求保持原数组顺序而第 491 题要求子序列必须是原数组的子序列排序会破坏相对顺序因此必须改用 Map 记录值的去重方案——这正是本题设计的精妙之处也是面试中常被追问的区分点。复杂度与边界分析从源码结构可以推断时间复杂度最坏情况下数组严格非递减且元素各不相同需要枚举 $2^n - n - 1$ 个长度 ≥ 2 的子序列每个结果都要做一次长度 O(k) 的拷贝总体为指数级 O(2^n · n)。题目将n限制在 15 以内正是为了确保指数级搜索在合理时间内完成空间复杂度递归深度最多为 n路径切片c与每层独立的visitedMap 占用 O(n) 辅助空间不计输出结果本身占用的空间边界情况严格递减数组输出空集全部元素相等的数组如[1,1,1]会生成所有长度 ≥ 2 的等值子序列单元素或空数组直接输出空集。在仓库中运行与验证仓库根目录的 go.mod 声明了模块github.com/halfrost/LeetCode-GoGo 1.19题解代码位于leetcode目录下的独立包中。如需本地验证本题可进入对应目录运行go test -v -run Test_Problem491 ./leetcode/0491.Non-decreasing-Subsequences/若想统计整个 leetcode 包的覆盖率仓库提供了 gotest.sh 脚本通过go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性生成合法的覆盖率文件coverage.txt。这也是 LeetCode-Go 项目“100% test coverage”目标的落地方式之一。小结第 491 题是“子序列 去重”类问题的集大成者它既考验 DFS 回溯模板的熟练度路径维护、深拷贝、剪枝又通过“不可排序”这一约束迫使我们理解 Map 去重与排序去重的适用场景差异。仓库 题解文档 与 源码实现 提供了一个完整、可复跑的最小范例建议结合第 78、90 题一起刷一通百通。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考