491. Non-decreasing Subsequences
给你一个 array nums，要你回传他的所有非严格递增的 subsequences，顺序任意
subsequence 长度至少要是 2
Example 1:
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Example 2:
Input: nums = [4,4,3,2,1]
Output: [[4,4]]
思路:
1.类似 DFS，每个 num[i] 都递回往后找挑与不挑的结果
目前的 subsequence 就放在参数里往下传就好
因为这题不要输出长相一样的 subsequence 所以不用 list 用 tuple 直接塞进 set 里
遇到出现过的 subsequence 也可以不用往下找(感觉有点疑虑不过应该是对的)
Python code:
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = set()
def dfs(idx, arr):
if len(arr) >= 2:
res.add(arr)
for i in range(idx+1, n):
tup = arr+(nums[i],)
if (idx == -1 or nums[i] >= nums[idx]) and tup not in res:
dfs(i, tup)
dfs(-1, ())
return res

大师

大师