We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Non-decreasing Subsequences

Difficulty: Medium

Problem Description

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.

Key Insights

  • A subsequence can be formed by deleting some or no elements from the array while maintaining the order of the remaining elements.
  • To ensure non-decreasing order, any added element must be greater than or equal to the last element of the current subsequence.
  • Using backtracking allows for exploring all potential subsequences efficiently.
  • A set can be utilized to avoid duplicate subsequences in the final result.

Space and Time Complexity

Time Complexity: O(2^N) - where N is the length of nums, as we explore all subsequences. Space Complexity: O(N) - for the recursion stack and storing results.

Solution

The solution employs a backtracking approach, where we recursively build subsequences. We start with an empty subsequence and try to include each element from the array, ensuring that we only add it if it maintains the non-decreasing order. We store the valid subsequences in a set to ensure uniqueness.

Code Solutions

def findSubsequences(nums):
    def backtrack(start, path):
        if len(path) > 1:
            res.add(tuple(path))  # Use a tuple to ensure uniqueness
        for i in range(start, len(nums)):
            if not path or nums[i] >= path[-1]:  # Ensure non-decreasing
                backtrack(i + 1, path + [nums[i]])

    res = set()
    backtrack(0, [])
    return list(map(list, res))  # Convert tuples back to lists
← Back to All Questions