目录

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

相似问题:

分析

递推得到所有递增子序列(包括单个元素),再去掉单元素序列即可。

解答

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