Watch 10 video solutions for Non-decreasing Subsequences, a medium level problem involving Array, Hash Table, Backtracking. This walkthrough by codestorywithMIK has 17,358 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |