Coding Interview PatternsIncreasing Subsequences
MediumSubsets
Increasing Subsequences
Explanation & Solution
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.
A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
Input:nums = [4,6,7,7]
0
4
1
6
2
7
3
7
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
Explanation: All non-decreasing subsequences with at least 2 elements are listed.
Constraints
1 <= nums.length <= 15-100 <= nums[i] <= 100
Approach
Subsets pattern
1. Initialize the Backtracking
- Create an empty result array to collect all valid subsequences.
- Start the recursive exploration from index 0 with an empty path.
2. Collect Valid Subsequences
- At each recursive call, if the current path has at least 2 elements, add a copy to the result.
- This captures all subsequences of length 2 and above.
3. Iterate Through Remaining Elements
- From the current starting index, try appending each remaining element.
- Non-decreasing check: Only append
nums[i]if it is greater than or equal to the last element in the path. - This ensures the subsequence remains non-decreasing.
4. Avoid Duplicates with a Set
- At each level of recursion, maintain a used Set.
- If
nums[i]has already been tried at this level, skip it. - This prevents generating duplicate subsequences without needing to sort the input.
5. Backtrack
- After exploring with
nums[i]included, remove it from the path. - Continue trying the next candidate element.
6. Return Sorted Result
- Sort the result lexicographically for consistent output.
- Return the final list of all unique non-decreasing subsequences.
Key Insight
- Unlike standard subsets, we cannot sort the input because the order of elements matters for subsequences.
- Instead, we use a per-level Set to avoid picking the same value twice at the same recursion depth.
Time
O(2^n * n)in the worst case we explore all subsequences.Space
O(n) for the recursion stack and path.Visualization
Input:
[4, 6, 7, 7]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps