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] <= 100This approach leverages a recursive backtracking method to explore all possible subsequences. The process involves recursively adding elements to the current subsequence and proceeding to the next elements only if they maintain a non-decreasing order. This approach ensures each subsequence is visited and non-decreasing ones are retained. To avoid duplication, a set or unique list is used for storing resulting subsequences.
The code defines a recursive function `backtrack` that explores all potential subsequences starting at each index of the array. It uses a set `res` to avoid duplicates. Subsequences are formed by gradually building and checking them to ensure they are non-decreasing before adding.
C++
Time Complexity: O(2^n), where n is the number of elements in the array, since each element can either be included or not in a subsequence.
Space Complexity: O(n*2^n) for storing all subsequences in the worst case.
This approach utilizes a bitmask technique to generate all possible subsequences iteratively. Each number's presence in a given subsequence is represented by a corresponding bit in a binary number, allowing for a systematic generation of potential subsequences. By iterating over all possible binary representations, the algorithm constructs and evaluates subsequences for their non-decreasing nature before storing them.
In JavaScript, this code leverages a `Set` to store unique sequences and iterates over the `mask` value representing all subsequences. The inner loop checks each bit of `mask` and includes the corresponding element if it fits the subsequence. It ensures non-decreasing order by comparing the last element of `sequence`.
Java
Time Complexity: O(n * 2^n) due to checking each subsequence for validity.
Space Complexity: O(n * 2^n) for storing all subsequences.
| Approach | Complexity |
|---|---|
| Recursive Backtracking | Time Complexity: O(2^n), where n is the number of elements in the array, since each element can either be included or not in a subsequence. Space Complexity: O(n*2^n) for storing all subsequences in the worst case. |
| Iterative with Bitmasking | Time Complexity: O(n * 2^n) due to checking each subsequence for validity. Space Complexity: O(n * 2^n) for storing all subsequences. |
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 432,482 views views
Watch 9 more video solutions →Practice Non-decreasing Subsequences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor