0491：非递减子序列（★）

力扣第 491 题

题目

给你一个整数数组 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

相似问题：

• 0646：最长数对链

分析

递推得到所有递增子序列（包括单个元素），再去掉单元素序列即可。

解答

1
2
3
4
5
6
7

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = set()
        for x in nums:
            res |= {A+(x,) for A in res if A[-1]<=x}
            res.add((x,))
        return [list(A) for A in res if len(A)>=2]

53 ms