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] <= 100Problem Overview: Given an integer array nums, return all different subsequences where the elements are in non-decreasing order and the subsequence length is at least 2. The challenge is not generating subsequences—that part is straightforward—but removing duplicates while preserving the non-decreasing constraint.
Approach 1: Recursive Backtracking with Set Pruning (O(2^n) time, O(n) recursion space)
This approach explores the subsequence decision tree using backtracking. At each index, you decide whether to include the current element in the growing subsequence. You only add a number if it keeps the sequence non-decreasing (nums[i] >= last_element). Duplicate subsequences are avoided by maintaining a set at each recursion level that tracks which values were already used at that depth. This prevents generating identical branches when the input contains repeated numbers. The algorithm iterates forward from the current index, recursively building sequences, and records results whenever the subsequence length reaches at least two. Time complexity is O(2^n) since every element can be included or skipped, and recursion stack space is O(n) while storing results may take additional space depending on output size.
Approach 2: Iterative Enumeration with Bitmasking (O(n * 2^n) time, O(n) space)
Another way to generate subsequences is by representing each subset with a binary mask using bit manipulation. For an array of length n, iterate from 0 to (1 << n) - 1. Each bitmask indicates which elements belong to the subsequence. While constructing the subsequence, verify two conditions: the length must be at least two and the numbers must be non-decreasing. To avoid duplicates caused by repeated values in the array, store generated subsequences in a hash-based structure such as a set, leveraging concepts from hash table deduplication. This approach is easy to implement and useful for understanding how subset enumeration works. However, validating order and deduplicating results adds overhead, resulting in O(n * 2^n) time complexity.
Recommended for interviews: Recursive backtracking with a per-level set is the expected solution. Interviewers want to see that you can generate subsequences while pruning duplicates efficiently. The brute-force bitmask approach demonstrates understanding of subset enumeration, but the backtracking solution shows stronger control of recursion, pruning, and state management—skills commonly evaluated in problems involving arrays and combinatorial search.
This 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.
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`.
JavaScript
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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Set | O(2^n) | O(n) | Best general solution. Efficient duplicate pruning and commonly expected in interviews. |
| Iterative Bitmask Enumeration | O(n * 2^n) | O(n) | Good for understanding subset generation or when implementing iterative solutions. |
Non-decreasing Subsequences | Khaandani Backtracking Template | Explanation | Live Coding • codestorywithMIK • 17,358 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