Non-decreasing Subsequences
MedPrompt
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] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach generates every possible subsequence of the input array. Then, it filters these subsequences based on two criteria: they must be non-decreasing, and they must have a length of at least two. To handle duplicate subsequences that might be formed, a Set is used to store the valid ones, ensuring uniqueness.
Algorithm
- Create a
Set<List<Integer>> resultSetto store unique valid subsequences. - Get the length
nof the input arraynums. - Iterate through all possible non-empty subsets using a bitmask
ifrom1to(1 << n) - 1. - For each bitmask
i, construct the corresponding subsequence:- Create an empty
List<Integer> subsequence. - Iterate from
j = 0ton - 1. If thej-th bit ofiis set, addnums[j]tosubsequence.
- Create an empty
- After constructing the
subsequence, validate it:- If
subsequence.size() < 2, discard it. - Check if the subsequence is non-decreasing. Iterate from the second element and ensure
subsequence[k] >= subsequence[k-1]. - If it is valid, add it to the
resultSet.
- If
- Finally, convert the
resultSetto aListand return it.
Walkthrough
The core of this method is to iterate through all 2^n subsets of the given array nums. We can achieve this using bit manipulation, where each integer from 1 to 2^n - 1 represents a bitmask. If the j-th bit in the mask is 1, it signifies that the j-th element of nums is included in the current subsequence.
For each generated subsequence, we perform two checks:
- Size Check: The subsequence must contain at least two elements.
- Non-decreasing Check: We iterate through the subsequence to ensure that each element is greater than or equal to the one preceding it.
If a subsequence satisfies both conditions, it is added to a Set<List<Integer>>. Using a Set conveniently handles the problem of duplicate subsequences, as a Set only stores unique elements. Finally, the contents of the Set are transferred to a List to match the required return type.
class Solution { public List<List<Integer>> findSubsequences(int[] nums) { Set<List<Integer>> resultSet = new HashSet<>(); int n = nums.length; for (int i = 1; i < (1 << n); i++) { List<Integer> subsequence = new ArrayList<>(); for (int j = 0; j < n; j++) { if (((i >> j) & 1) == 1) { subsequence.add(nums[j]); } } if (subsequence.size() >= 2) { boolean isNonDecreasing = true; for (int k = 1; k < subsequence.size(); k++) { if (subsequence.get(k) < subsequence.get(k - 1)) { isNonDecreasing = false; break; } } if (isNonDecreasing) { resultSet.add(subsequence); } } } return new ArrayList<>(resultSet); }}Complexity
Time
O(n * 2^n). We iterate through `2^n` potential subsequences. For each, building the subsequence takes O(n) time, and validating it also takes O(n). Adding a list of size `k` to a hash set takes O(k) time. Thus, the overall complexity is dominated by this exponential factor.
Space
O(n * 2^n). In the worst-case scenario (e.g., a sorted array of unique elements), the `resultSet` might need to store a number of subsequences on the order of `2^n`, with each subsequence having a length up to `n`.
Trade-offs
Pros
Conceptually simple and straightforward to implement.
Guaranteed to find all valid subsequences.
Cons
Extremely inefficient due to its O(n * 2^n) time complexity, making it unsuitable for
nlarger than about 20.Generates a vast number of subsequences that are immediately discarded, wasting computation.
High space complexity to store all generated subsequences before filtering and then storing the results.
This approach uses recursion (backtracking) to build the non-decreasing subsequences more intelligently. Instead of generating every subsequence and then filtering, we only extend the current subsequence with elements that maintain the non-decreasing property. A Set is still used for the final result to automatically handle duplicates that might arise from identical numbers in the input array (e.g., in [4, 7, 7], [4, 7] can be formed in two ways).
Algorithm
- Initialize a
Set<List<Integer>> resultto store the final unique subsequences. - Define a recursive helper function,
backtrack(index, currentList). - The
indexparameter tracks the current position in thenumsarray, andcurrentListis the subsequence being built. - In the
backtrackfunction:- If
currentList.size() >= 2, it's a valid subsequence, so add a copy of it to theresultset. - Iterate through
numsfromi = indexto the end. - For each element
nums[i], check if it can extend the current subsequence:currentListmust be empty, ornums[i]must be greater than or equal to the last element ofcurrentList. - If the condition is met, add
nums[i]tocurrentListand make a recursive call:backtrack(i + 1, currentList). - After the recursive call returns, remove
nums[i]fromcurrentListto backtrack and explore other possibilities.
- If
- Start the process by calling
backtrack(0, new ArrayList<>()). - Return a
Listcreated from theresultset.
Walkthrough
A recursive helper function, say backtrack(index, currentList), forms the foundation of this method. The index parameter indicates the starting position in the nums array from which to select the next element, and currentList holds the subsequence constructed so far.
The recursion proceeds as follows:
- First, we check if the
currentListhas at least two elements. If so, it's a valid result, and we add a copy of it to a globalSet<List<Integer>>. - Next, we loop from the current
indexto the end of thenumsarray. For each elementnums[i], we check if adding it tocurrentListwould maintain the non-decreasing order. This is true ifcurrentListis empty or ifnums[i]is greater than or equal to the last element incurrentList. - If
nums[i]is a valid candidate, we add it tocurrentListand make a recursive call for the rest of the array:backtrack(i + 1, currentList). - Upon returning from the recursive call, we remove
nums[i]fromcurrentList. This backtracking step is crucial as it allows us to explore other subsequences that don't includenums[i]at this position.
class Solution { private Set<List<Integer>> result; private int[] nums; public List<List<Integer>> findSubsequences(int[] nums) { this.result = new HashSet<>(); this.nums = nums; backtrack(0, new ArrayList<>()); return new ArrayList<>(result); } private void backtrack(int index, List<Integer> current) { if (current.size() >= 2) { result.add(new ArrayList<>(current)); } for (int i = index; i < nums.length; i++) { if (current.isEmpty() || nums[i] >= current.get(current.size() - 1)) { current.add(nums[i]); backtrack(i + 1, current); current.remove(current.size() - 1); } } }}Complexity
Time
O(n * 2^n). The recursion tree can have up to `2^n` nodes. At each valid terminal node, we add a list to the set, which takes O(n) for hashing. While better than brute-force, the complexity remains exponential.
Space
O(n * 2^n). The recursion depth is O(n). The main space is consumed by the `result` set, which can store up to O(2^n) subsequences, each of length up to O(n).
Trade-offs
Pros
More efficient than the brute-force approach because it prunes branches that would lead to non-decreasingly sorted subsequences.
The logic directly maps to the problem of building sequences incrementally.
Cons
Relies on a
Setto handle duplicates, which involves hashing entire lists. This can be less performant than preventing duplicate generation in the first place.It explores redundant recursive paths when the input array contains duplicate numbers, leading to unnecessary computations.
This is the most efficient approach, building upon the backtracking method. It cleverly avoids generating duplicate subsequences from the start, which eliminates the need for a final Set for deduplication. The key is to track which numbers have already been used at the current level of the recursion, thereby pruning the search space.
Algorithm
- Initialize a
List<List<Integer>> result. - Define a recursive helper function
backtrack(index, currentList). - In the
backtrackfunction:- If
currentList.size() >= 2, add a copy to theresultlist. - To prevent duplicates at the current level of recursion, initialize a local
Set<Integer> usedInThisLevel. - Iterate through
numsfromi = indexto the end. - For each element
nums[i], apply two checks:- Non-decreasing check:
currentListmust be empty ornums[i]must be>=the last element ofcurrentList. - Duplicate check: The number
nums[i]must not have been used at this specific recursive depth yet. Check this using!usedInThisLevel.contains(nums[i]).
- Non-decreasing check:
- If both checks pass:
- Mark
nums[i]as used for this level:usedInThisLevel.add(nums[i]). - Add
nums[i]tocurrentList. - Make the recursive call:
backtrack(i + 1, currentList). - Backtrack by removing
nums[i]fromcurrentList.
- Mark
- If
- Start the process by calling
backtrack(0, new ArrayList<>()). - Return the
resultlist.
Walkthrough
This optimized backtracking approach refines the previous one by handling duplicates during the recursive construction itself. The main recursive function backtrack(index, currentList) remains, but with an added mechanism for deduplication.
Inside each call to backtrack, we introduce a local Set<Integer> called usedInThisLevel. This set's purpose is to keep track of the numbers we have already chosen to extend the subsequence at the current decision point.
When we iterate from i = index to the end of the array, for each element nums[i], we first check if it maintains the non-decreasing property. If it does, we then check if nums[i] is already in usedInThisLevel. If it is, it means we have already explored all possible subsequences starting with the current prefix followed by nums[i]. For example, if the prefix is [4] and the remaining array is [..., 7, ..., 7], once we process the first 7, we add it to usedInThisLevel and won't process the second 7 for the same prefix [4]. This effectively prunes the search tree and prevents duplicate subsequences from ever being generated.
class Solution { private List<List<Integer>> result; private int[] nums; public List<List<Integer>> findSubsequences(int[] nums) { this.result = new ArrayList<>(); this.nums = nums; backtrack(0, new ArrayList<>()); return result; } private void backtrack(int index, List<Integer> current) { if (current.size() >= 2) { result.add(new ArrayList<>(current)); } // This set tracks numbers used at the current level of recursion // to avoid duplicate subsequences. Set<Integer> usedInThisLevel = new HashSet<>(); for (int i = index; i < nums.length; i++) { // Maintain non-decreasing order if (current.isEmpty() || nums[i] >= current.get(current.size() - 1)) { // Skip if the current number has been used at this level if (usedInThisLevel.contains(nums[i])) { continue; } usedInThisLevel.add(nums[i]); current.add(nums[i]); backtrack(i + 1, current); current.remove(current.size() - 1); } } }}Complexity
Time
O(n * 2^n). While the worst-case complexity is the same (for an array with unique, sorted elements), this approach is much faster in practice for inputs with duplicates because it prunes large parts of the recursion tree. The work per node is dominated by list copying (O(n)).
Space
O(n * 2^n). The space is dominated by the `result` list. The recursion stack uses O(n) space, and each `usedInThisLevel` set uses at most O(k) space where k is the number of unique elements in the range `[-100, 100]`, which is constant in this problem.
Trade-offs
Pros
Most efficient solution by preventing duplicate work, making it significantly faster for inputs with repeated numbers.
Avoids the overhead of using a
Setfor the final results and hashing lists.Directly builds the final, unique list of subsequences.
Cons
The logic is slightly more complex due to the need to manage the
usedInThisLevelset at each step of the recursion.The worst-case time and space complexity are still exponential, which is inherent to the problem of finding all subsequences.
Solutions
Solution
class Solution {private int[] nums;private List<List<Integer>> ans;public List<List<Integer>> findSubsequences(int[] nums) { this.nums = nums; ans = new ArrayList<>(); dfs(0, -1000, new ArrayList<>()); return ans; }private void dfs(int u, int last, List<Integer> t) { if (u == nums.length) { if (t.size() > 1) { ans.add(new ArrayList<>(t)); } return; } if (nums[u] >= last) { t.add(nums[u]); dfs(u + 1, nums[u], t); t.remove(t.size() - 1); } if (nums[u] != last) { dfs(u + 1, last, t); } }}class Solution {public: vector<vector<int>> findSubsequences(vector<int> &nums) { vector<vector<int>> ans; vector<int> t; dfs(0, -1000, t, nums, ans); return ans; } void dfs(int u, int last, vector<int> &t, vector<int> &nums, vector<vector<int>> &ans) { if (u == nums.size()) { if (t.size() > 1) ans.push_back(t); return; } if (nums[u] >= last) { t.push_back(nums[u]); dfs(u + 1, nums[u], t, nums, ans); t.pop_back(); } if (nums[u] != last) dfs(u + 1, last, t, nums, ans); }};class Solution: def findSubsequences(self, nums: List[int]) -> List[List[int]]: def dfs(u, last, t): if u == len(nums): if len(t) > 1: ans . append(t[:]) return if nums[u] >= last: t . append(nums[u]) dfs(u + 1, nums[u], t) t . pop() if nums[u] != last: dfs(u + 1, last, t) ans = [] dfs(0, - 1000, []) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.