491.md

491 Increasing Subsequences

Description

link

---

Solution

其实这题的核心在于如何去重，答案提供者很巧妙使用了一个方法，就是Tuple，因为Tuple本身是可以直接去重的，(5,)这种表示形式表示该Tuple只有一个数字，等待添加，记得每次保留空Tuple以添加下一个单数字

元组相加操作即是按顺序合并两个tuple

这里讲一下DFS的时间复杂度判断：如果是最坏情况的话，首先因为初始DFS的循环是O(M + N)，每个点的最大遍历长度是O(MN)，这就是最坏情况的时间复杂度

---

Code

最坏情况下是O(n^2)

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        subs = {()}
        for num in nums:
            subs |= {sub + (num,)
                     for sub in subs
                     if not sub or sub[-1] <= num}
        return [sub for sub in subs if len(sub) >= 2]