Leetcode 491. Increasing Subsequ

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

1. Description

Increasing Subsequences

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)

Reference

1. https://leetcode.com/problems/increasing-subsequences/