491. Non-decreasing Subsequences

MediumLeetCode

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

How to solve the problem

• Backtracking (DFS)

Code

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)