LeetCode 491. 非递减子序列 - Java 实现思路分析这道题是回溯 同层去重的经典题目。几个关键点子序列不要求连续但要保持原有顺序所以不能对原数组排序这点和 LeetCode 90 不同。非递减当前选中的数 nums[i] 必须 路径中最后一个数。去重由于不能排序需要在同一层递归中用 Set 记录本层已用过的数字避免相同数字在同一层被重复选同一层的相同数字会生成相同的子序列。代码实现classSolution{privateListListIntegerresultnewArrayList();privateListIntegerpathnewArrayList();publicListListIntegerfindSubsequences(int[]nums){backtrack(nums,0);returnresult;}privatevoidbacktrack(int[]nums,intstart){// 路径长度 2 时即为一个合法答案if(path.size()2){result.add(newArrayList(path));}// 本层去重集合记录同一层中已经使用过的数字SetIntegerusednewHashSet();for(intistart;inums.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,i1);path.remove(path.size()-1);}}}代码要点说明为什么 used 定义在 backtrack 方法内部used 只在当前这一层有效。因为同一层的两个相同数字比如 [4, 7, 6, 7] 中的两个 7选择它们之后接下去的选择范围完全不同吗不是相同的 —— 它们后面可选的元素完全一致因此产生的子序列完全相同必须去重。而放在方法内部每层新建一个 Set恰好实现同层去重、不同层不去重的效果。used.add(nums[i]) 的位置必须在通过非递减检查之后再加。原因是如果 nums[i] 因为太小而跳过同层后面相同的数也一定因同样原因被跳过提前标记反而没什么问题但为了逻辑清晰used 表示本层真正使用过的放在通过检查之后更严谨。为什么不能先排序子序列是有顺序要求的。若先排序就变成了求子集与原题需求不符。这也是本题和 LeetCode 90子集 II先排序再去重的核心区别。复杂度分析· 时间复杂度最坏情况下 O(2^n * n)其中 n 为数组长度构造每个答案需 O(n)但由于去重剪枝实际远小于此上界。· 空间复杂度O(n)递归深度为 nused 集合每层最多存 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[]usednewint[201];// 时间戳法避免每层重新分配或者直接把 int[] used new int[201] 定义在 backtrack 内部用 -101 初始化表示未用也是可以的。不过 HashSet 写法更通用、更简洁面试中完全够用。
