回溯中等1 种解法

#491非递减子序列

找出数组中所有长度至少为 2 的不同非递减子序列，同时保持原下标顺序。

#回溯#数组#子序列#哈希集合

解题主线

不能排序原数组，因为子序列必须保持原始相对顺序。

每一递归层创建独立 Set，跳过该层已经作为下一项选择过的数值。

路径非空时，只有不小于路径末项的候选才能继续扩展。

解法 1：同层哈希去重回溯

按下标向后枚举，用路径末值保证非递减，并用当前层的 HashSet 去掉相同下一项。

时间复杂度

O(n × 2^n)，最坏枚举并复制所有子序列

空间复杂度

O(n²)，递归深度为 n，每层最坏保留 O(n) 个去重值；不计输出

491. 非递减子序列 · 同层哈希去重回溯

java

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);
        }
    }
}

按下标向后枚举，用路径末值保证非递减，并用当前层的 HashSet 去掉相同下一项。

边界与易错点

相邻重复判断不适用：重复值在原数组中可能并不相邻。
同层 Set 不能跨递归层共享，否则会误删不同前缀下的合法选择。
长度达到 2 后应收集当前路径，但仍要继续扩展更长子序列。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q491_findSubsequences.java