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