Increasing Subsequences

Intuition

Solution

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        edges = [[] for _ in range(len(nums))]
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[j] >= nums[i]:
                    edges[i].append(j)

        all_path = []
        for i in range(len(nums)):
            all_path.extend(self._dfs(edges, i))

        ans = []
        for path in all_path:
            if len(path) == 1:
                continue
            tmp = []
            for p in path:
                tmp.append(nums[p])
            ans.append(tmp)
        ans = set([tuple(path) for path in ans])
        ans = [list(path) for path in ans]
        ans.sort()
        return ans

    def _dfs(self, edges, node):
        ans = [[node]]
        for child in edges[node]:
            for sub in self._dfs(edges, child):
                ans.append([node] + sub)
        return ans