491. 非递减子序列
题目描述
输入整数数组 nums，其中可能有重复值。
子序列是从数组中删去若干元素（也可以不删）后、保持原有顺序得到的序列。找出所有元素个数至少为 2、且从前到后不下降的子序列；相邻两项相等也符合要求。
返回这些子序列，内容相同的子序列只保留一份。答案中子序列的排列顺序不限。
示例 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]]
解释：共有 8 个不同的非递减子序列，两个 7 组成的 [7,7] 也算在内。
示例 2
输入：nums = [4,4,3,2,1] 输出：[[4,4]]
解释：只有两个 4 能组成非递减子序列。
数据范围
1 <= nums.length <= 15-100 <= nums[i] <= 100
解题思路：回溯 + 同层去重
回溯：dfs(start) 从 start 往后挑下一个元素接到 path 末尾。比 path 末尾小的不能接；同一层里已经用过的数值再接一次会得到重复的子序列，用本层的 used 集合跳过。每进入一层，若 path 长度 ≥ 2 就记录一份。不能排序，因为子序列必须保持原数组顺序。
为什么正确
path 是 nums 的一个非递减子序列，且每一层 used 记录了本层已作为“下一个元素”尝试过的数值，所以同一个子序列只会被生成一次。
复杂度分析
时间 O(2^n · n)：最多 2^n 个子序列，每个复制 O(n)；空间 O(n) 递归栈与 path（不计结果）。
易错点
不能像子集 II 那样先排序再跳过相邻重复——排序会破坏原顺序；去重集合必须是每层新建的，而不是全局的。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def dfs(start):
if len(path) >= 2:
res.append(path[:])
used = set()
for i in range(start, len(nums)):
if path and nums[i] < path[-1]:
continue
if nums[i] in used:
continue
used.add(nums[i])
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return resclass Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
dfs(nums, 0);
return res;
}
void dfs(int[] nums, int start) {
if (path.size() >= 2) {
res.add(new ArrayList<>(path));
}
Set<Integer> used = new HashSet<>();
for (int i = start; i < nums.length; i++) {
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
continue;
}
if (used.contains(nums[i])) {
continue;
}
used.add(nums[i]);
path.add(nums[i]);
dfs(nums, i + 1);
path.remove(path.size() - 1);
}
}
}class Solution {
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums, int start) {
if (path.size() >= 2) {
res.push_back(path);
}
unordered_set<int> used;
for (int i = start; i < (int)nums.size(); i++) {
if (!path.empty() && nums[i] < path.back()) {
continue;
}
if (used.count(nums[i])) {
continue;
}
used.insert(nums[i]);
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
dfs(nums, 0);
return res;
}
};func findSubsequences(nums []int) [][]int {
res := [][]int{}
path := []int{}
var dfs func(start int)
dfs = func(start int) {
if len(path) >= 2 {
res = append(res, append([]int{}, path...))
}
used := map[int]bool{}
for i := start; i < len(nums); i++ {
if len(path) > 0 && nums[i] < path[len(path)-1] {
continue
}
if used[nums[i]] {
continue
}
used[nums[i]] = true
path = append(path, nums[i])
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(0)
return res
}var findSubsequences = function(nums) {
const res = [];
const path = [];
const dfs = (start) => {
if (path.length >= 2) {
res.push([...path]);
}
const used = new Set();
for (let i = start; i < nums.length; i++) {
if (path.length && nums[i] < path[path.length - 1]) {
continue;
}
if (used.has(nums[i])) {
continue;
}
used.add(nums[i]);
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
};
dfs(0);
return res;
};function findSubsequences(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const dfs = (start: number): void => {
if (path.length >= 2) {
res.push([...path]);
}
const used = new Set<number>();
for (let i = start; i < nums.length; i++) {
if (path.length && nums[i] < path[path.length - 1]) {
continue;
}
if (used.has(nums[i])) {
continue;
}
used.add(nums[i]);
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
};
dfs(0);
return res;
}其他解法
回溯在搜索过程中用“同一层不选相同的数”去重并剪掉递减分支；二进制枚举先生成全部子集，再用哈希集合事后去重，更暴力也更好理解。
解法 2：二进制枚举 + 哈希去重 时间 O(2ⁿ·n)，空间 O(2ⁿ·n)
用 n 位二进制数枚举所有子序列，第 i 位为 1 表示选择 nums[i]。对每个子序列检查长度是否至少为 2、是否非递减。合法的子序列转成可哈希的键放入集合，重复出现的序列只保留第一次。
思路最直接，不需要考虑回溯中的去重规则。每个子集都要完整生成和检查，并要用哈希集合存下所有结果来去重，额外空间大。
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
seen = set()
res = []
# 用 n 位二进制数枚举所有子序列
for mask in range(1, 1 << n):
seq = [nums[i] for i in range(n) if mask >> i & 1]
if len(seq) < 2:
continue
if any(seq[i] > seq[i + 1] for i in range(len(seq) - 1)):
continue
key = tuple(seq)
# 哈希集合去重：相同的序列只保留一次
if key not in seen:
seen.add(key)
res.append(seq)
return resclass Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
int n = nums.length;
Set<List<Integer>> seen = new HashSet<>();
List<List<Integer>> res = new ArrayList<>();
for (int mask = 1; mask < (1 << n); mask++) {
List<Integer> seq = new ArrayList<>();
boolean ok = true;
for (int i = 0; i < n && ok; i++) {
if ((mask >> i & 1) == 0) continue;
if (!seq.isEmpty() && seq.get(seq.size() - 1) > nums[i]) ok = false;
seq.add(nums[i]);
}
if (ok && seq.size() >= 2 && seen.add(seq)) res.add(seq);
}
return res;
}
}class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
int n = nums.size();
set<vector<int>> seen;
vector<vector<int>> res;
for (int mask = 1; mask < (1 << n); mask++) {
vector<int> seq;
bool ok = true;
for (int i = 0; i < n && ok; i++) {
if (!(mask >> i & 1)) continue;
if (!seq.empty() && seq.back() > nums[i]) ok = false;
seq.push_back(nums[i]);
}
if (ok && seq.size() >= 2 && seen.insert(seq).second) res.push_back(seq);
}
return res;
}
};func findSubsequences(nums []int) [][]int {
n := len(nums)
seen := map[string]bool{}
res := [][]int{}
for mask := 1; mask < 1<<n; mask++ {
seq := []int{}
key := []byte{}
ok := true
for i := 0; i < n && ok; i++ {
if mask>>i&1 == 0 {
continue
}
if len(seq) > 0 && seq[len(seq)-1] > nums[i] {
ok = false
}
seq = append(seq, nums[i])
// nums[i] 在 [-100, 100]，平移后用一个字节编码
key = append(key, byte(nums[i]+100))
}
if ok && len(seq) >= 2 && !seen[string(key)] {
seen[string(key)] = true
res = append(res, seq)
}
}
return res
}var findSubsequences = function(nums) {
const n = nums.length;
const seen = new Set();
const res = [];
for (let mask = 1; mask < (1 << n); mask++) {
const seq = [];
let ok = true;
for (let i = 0; i < n && ok; i++) {
if (!(mask >> i & 1)) continue;
if (seq.length && seq[seq.length - 1] > nums[i]) ok = false;
seq.push(nums[i]);
}
if (!ok || seq.length < 2) continue;
const key = seq.join(',');
if (!seen.has(key)) {
seen.add(key);
res.push(seq);
}
}
return res;
};function findSubsequences(nums: number[]): number[][] {
const n = nums.length;
const seen = new Set<string>();
const res: number[][] = [];
for (let mask = 1; mask < (1 << n); mask++) {
const seq: number[] = [];
let ok = true;
for (let i = 0; i < n && ok; i++) {
if (!(mask >> i & 1)) continue;
if (seq.length && seq[seq.length - 1] > nums[i]) ok = false;
seq.push(nums[i]);
}
if (!ok || seq.length < 2) continue;
const key = seq.join(',');
if (!seen.has(key)) {
seen.add(key);
res.push(seq);
}
}
return res;
}