491. Non-decreasing Subsequences
MediumLeetCodeGiven 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
How to solve the problem
- Backtracking (DFS)
Code
Python
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
path = [] # Current sequence being constructed
result = []
def backtracking(nums, startIndex, path, result):
# If the current path contains at least two elements, it's a valid answer
if len(path) > 1:
result.append(path[:]) # Append a copy of path to result
coveredSet = set() # Used to avoid duplicate elements at the same recursion depth
for i in range(startIndex, len(nums)):
# If the current number is smaller than the last in path, or has been used at this level, skip it
if (path and nums[i] < path[-1]) or nums[i] in coveredSet:
continue
coveredSet.add(nums[i]) # Mark nums[i] as used for this recursion depth
path.append(nums[i]) # Choose nums[i], add to current path
backtracking(nums, i + 1, path, result) # Explore further with nums[i] included
path.pop() # Undo the choice (backtrack), try next possible number
backtracking(nums, 0, path, result)
return result
Complexity
- Time complexity: O(2^n * n)
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!