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

大師

大師