LeetCode-python 491.递增子序列

题目链接
难度:中等       类型: 数组、深度优先搜索


给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。

示例

输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

解题思路


类似于求所有子序列
只多了两个条件:

  1. 在添加一个元素时,只需考虑它是否大于等于当前子序列的最后一个值
  2. 子序列长度大于2

注意:
记录用过的数字,避免重复

代码实现

class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.n = len(nums)
        def dfs(index, path):
            if len(path)>=2:
                res.append(path)
      
            if index>=self.n:
                return
            used = {}
            for i in range(index, self.n):
                if nums[i] in used: continue
                used[nums[i]] = True
                if not path or nums[i]>=path[-1] :
                    dfs(i+1, path+[nums[i]])
        dfs(0, [])
        return res

本文链接://www.greatytc.com/p/8fa9e12a5f28

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容