企业官网建设流程全解析

LeetCode 491. 非递减子序列 - Java 实现

思路分析

这道题是回溯 + 同层去重的经典题目。几个关键点：

1. 子序列：不要求连续，但要保持原有顺序，所以不能对原数组排序（这点和 LeetCode 90 不同）。
2. 非递减：当前选中的数 nums[i] 必须 >= 路径中最后一个数。
3. 去重：由于不能排序，需要在同一层递归中用 Set 记录本层已用过的数字，避免相同数字在同一层被重复选（同一层的相同数字会生成相同的子序列）。

代码实现

classSolution{privateList<List<Integer>>result=newArrayList<>();privateList<Integer>path=newArrayList<>();publicList<List<Integer>>findSubsequences(int[]nums){backtrack(nums,0);returnresult;}privatevoidbacktrack(int[]nums,intstart){// 路径长度 >= 2 时即为一个合法答案if(path.size()>=2){result.add(newArrayList<>(path));}// 本层去重集合：记录同一层中已经使用过的数字Set<Integer>used=newHashSet<>();for(inti=start;i<nums.length;i++){// 同层去重if(used.contains(nums[i])){continue;}// 非递减约束if(!path.isEmpty()&&nums[i]<path.get(path.size()-1)){continue;}used.add(nums[i]);path.add(nums[i]);backtrack(nums,i+1);path.remove(path.size()-1);}}}

代码要点说明

1. 为什么 used 定义在 backtrack 方法内部？

used 只在当前这一层有效。因为同一层的两个相同数字（比如 [4, 7, 6, 7] 中的两个 7）选择它们之后接下去的选择范围完全不同吗？不，是相同的 —— 它们后面可选的元素完全一致，因此产生的子序列完全相同，必须去重。

而放在方法内部（每层新建一个 Set），恰好实现"同层去重、不同层不去重"的效果。

2. used.add(nums[i]) 的位置

必须在通过"非递减"检查之后再加。原因是：如果 nums[i] 因为太小而跳过，同层后面相同的数也一定因同样原因被跳过，提前标记反而没什么问题；但为了逻辑清晰（used 表示"本层真正使用过的"），放在通过检查之后更严谨。

3. 为什么不能先排序？

子序列是有顺序要求的。若先排序，就变成了求"子集"，与原题需求不符。这也是本题和 LeetCode 90（子集 II，先排序再去重）的核心区别。

复杂度分析

· 时间复杂度：最坏情况下 O(2^n * n)，其中 n 为数组长度（构造每个答案需 O(n)），但由于去重剪枝，实际远小于此上界。
· 空间复杂度：O(n)，递归深度为 n，used 集合每层最多存 n 个元素。

示例验证

输入 nums = [4, 6, 7, 7]，输出：

[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

[4,6,7] 和 [4,6,7]（来自两个不同的 7）会被 used 去重，只保留一份，符合题意。

优化技巧（可选）

由于题目数据范围有限（-100 <= nums[i] <= 100），可以用数组替代 HashSet 提速：

int[]used=newint[201];// 时间戳法，避免每层重新分配

或者直接把 int[] used = new int[201] 定义在 backtrack 内部，用 -101 初始化表示未用，也是可以的。不过 HashSet 写法更通用、更简洁，面试中完全够用。