LeetCode-Go 题解 | 491. Non-decreasing Subsequences：DFS 回溯与双重 Map 去重求解非递减子序列

LeetCode-Go 题解 | 491. Non-decreasing Subsequences：DFS 回溯与双重 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]]

注意：

1. 给定数组的长度不会超过 15；
2. 数组中的整数范围是 [-100, 100]；
3. 给定数组中可能包含重复数字，相等的数字应被视为递增的一种特殊情况（即允许非严格递增）。

这里的关键点在于：本题不要求最终结果按字典序或任何特定顺序输出，但要求所有子序列必须是互不相同的集合（去重），且元素顺序必须与原数组中的相对下标顺序一致。

解题思路概述

本题思路在 题解文档 中给出明确指引：它与第 78 题（Subsets）和第 90 题（Subsets II）是同一类问题。第 78、90 题求的是所有子序列，本题在此基础上额外增加了两个约束：

• 非递减：要求子序列内部满足nums[i] <= nums[j]（i < j），即允许相等；
• 长度限制：最终只输出长度 ≥ 2 的子序列。

需要注意的两个难点：

1. 原数组元素可能重复，直接 DFS 会产出大量重复解，最终输出必须去重；
2. 不能先排序再搜索——因为子序列必须保持原数组的相对顺序，排序会破坏下标顺序（这正是它与第 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 }

递归函数的四个关键点：

1. 加入当前元素：c = append(c, nums[current])，将当前下标对应的值追加到路径中；
2. 收集结果：只要当前路径长度 ≥ 2，就深拷贝一份（make+copy）存入res。注意这里使用深拷贝非常关键——因为c是复用的切片，后续递归会修改它，若不拷贝最终保存的将是同一块底层数组；
3. 非递减剪枝：if nums[current] <= nums[i]保证只向值不小于当前元素的后续元素递归，从而天然满足非递减（含相等）约束；
4. 层内去重：每一层递归新建一个局部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-Go（Go 1.19），题解代码位于leetcode目录下的独立包中。如需本地验证本题，可进入对应目录运行：

go test -v -run Test_Problem491 ./leetcode/0491.Non-decreasing-Subsequences/

若想统计整个 leetcode 包的覆盖率，仓库提供了 gotest.sh 脚本，通过go test -covermode=atomic -coverprofile=coverage.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