回溯中等1 种解法
#491非递减子序列
找出数组中所有长度至少为 2 的不同非递减子序列，同时保持原下标顺序。
#回溯#数组#子序列#哈希集合
原题
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：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]]
示例 2：
输入：nums = [4,4,3,2,1] 输出：[[4,4]]
提示：
1 <= nums.length <= 15-100 <= nums[i] <= 100
解题主线
- 不能排序原数组，因为子序列必须保持原始相对顺序。
- 每一递归层创建独立 Set，跳过该层已经作为下一项选择过的数值。
- 路径非空时，只有不小于路径末项的候选才能继续扩展。
解法 1：同层哈希去重回溯
按下标向后枚举，用路径末值保证非递减，并用当前层的 HashSet 去掉相同下一项。
-
时间复杂度： O(n × 2^n)，最坏枚举并复制所有子序列
-
空间复杂度： O(n²)，递归深度为 n，每层最坏保留 O(n) 个去重值；不计输出
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
final class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start,
List<Integer> path, List<List<Integer>> result) {
// 长度达标即收集，但仍继续向下扩展更长子序列。
if (path.size() >= 2) {
result.add(new ArrayList<>(path));
}
// 集合只服务当前递归层，去掉相同前缀下的重复下一项。
Set<Integer> usedAtThisDepth = new HashSet<>();
for (int i = start; i < nums.length; i++) {
// 候选小于路径末值会破坏非递减不变量。
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
continue;
}
if (!usedAtThisDepth.add(nums[i])) {
continue;
}
path.add(nums[i]);
backtrack(nums, i + 1, path, result);
// 回到父层时恢复路径，使下一个候选共享同一前缀。
path.remove(path.size() - 1);
}
}
}边界与易错点
- 相邻重复判断不适用：重复值在原数组中可能并不相邻。
- 同层 Set 不能跨递归层共享，否则会误删不同前缀下的合法选择。
- 长度达到 2 后应收集当前路径，但仍要继续扩展更长子序列。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q491_findSubsequences.java