491. Non-decreasing Subsequences
Đề Bài
Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.
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]]
Constraints:
1 <= nums.length <= 15-100 <= nums[i] <= 100
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(2ⁿ)
💾 Không gian
O(n)
Lời Giải
Python
0491-non-decreasing-subsequences.py
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = set()
def backTracking(i: int, path: List[int]) -> None:
if len(path) >= 2:
ans.add(tuple(path))
if i >= n:
return
for j in range(i, n):
if not path or nums[j] >= path[-1]:
backTracking(j + 1, path + [nums[j]])
backTracking(0, [])
return ans