Leetcode 491. Increasing Subsequences

Tyan

发布于 2021-08-06 15:28:56

5950

文章被收录于专栏：SnailTyanSnailTyan

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**Version 1，采用广度优先搜索，以列表中的每个元素为起点，寻找其后大于等于当前元素的数值，添加到当前列表中，并将当前列表添加到结果中，以当前列表以及下一个元素为起点，进行下一次广度优先搜索。最后，由于存在重复元素，因此需要对嵌套列表进行去重。

Version 1

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        for i in range(len(nums)):
            self.bfs(nums, i+1, [nums[i]], result)
        return [list(t) for t in set(tuple(_) for _ in result)]


    def bfs(self, nums, start, pre, result):
        for i in range(start, len(nums)):
            if nums[i] >= pre[-1]:
                temp = pre + [nums[i]]
                result.append(temp)
                self.bfs(nums, i+1, temp, result)