LeetCode 题解工作台
非递减子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。 示例 1： 输入： nums = [4,6,7,7] 输出： [[4,6],[4,6,…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
DFS 递归枚举每个数字选中或不选中，这里需要满足两个条件： 1. 子序列需要递增（非严格递增），因此序列的后一个数要大于等于前一个数；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一：DFS
DFS 递归枚举每个数字选中或不选中，这里需要满足两个条件：
- 子序列需要递增（非严格递增），因此序列的后一个数要大于等于前一个数；
- 子序列需要去重，这里重复的问题在于前后两个数相等并且不选中的情况，我们只在前后两个数不等的情况下，执行不选中的操作即可达到去重的效果。
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
def dfs(u, last, t):
if u == len(nums):
if len(t) > 1:
ans.append(t[:])
return
if nums[u] >= last:
t.append(nums[u])
dfs(u + 1, nums[u], t)
t.pop()
if nums[u] != last:
dfs(u + 1, last, t)
ans = []
dfs(0, -1000, [])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate effectively applies backtracking and hash table usage to avoid redundant subsequences.
- question_mark
The solution scales well to the upper constraint, showing consideration of optimization techniques like pruning.
- question_mark
The candidate demonstrates a clear understanding of array scanning and how it helps ensure subsequences remain non-decreasing.
常见陷阱
外企场景- error
Failure to track unique subsequences leading to repeated results.
- error
Not pruning the recursion tree early enough, causing excessive computational overhead.
- error
Incorrect handling of edge cases such as arrays with duplicate elements.
进阶变体
外企场景- arrow_right_alt
Modify the problem to allow subsequences of length one.
- arrow_right_alt
Expand the problem to allow strictly increasing subsequences only.
- arrow_right_alt
Add a constraint where subsequences must sum to a target value.