Non-decreasing Subsequences: Backtracking with Deduplication
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.
This is LeetCode 491: Non-decreasing Subsequences. For example, given nums = [4, 6, 7, 7], you should return [[4,6], [4,6,7], [4,6,7,7], [4,7], [4,7,7], [6,7], [6,7,7], [7,7]]. The tricky part is not building the subsequences themselves - it is avoiding duplicate results when the input contains repeated values.
Why sorting does not work here
If you have solved Subsets II or Combination Sum II, your instinct might be to sort the array first and then use the classic if i > start and nums[i] == nums[i - 1]: continue guard. That approach works perfectly for those problems. But here it fails for a fundamental reason: the problem asks for subsequences, which means you must preserve the original order of elements. Sorting destroys that order.
Consider nums = [4, 3, 2, 1]. No non-decreasing subsequence of length two or more exists. But if you sorted it to [1, 2, 3, 4], you would incorrectly find many. The relative order matters, so you cannot sort.
This means you need a different deduplication strategy.
The key insight
Instead of sorting and comparing adjacent elements, use a set at each recursion level to track which values you have already tried at that level. Before picking a value to extend the current subsequence, check whether that value is already in the set. If it is, skip it. If not, add it and recurse.
This per-level set replaces the sorted duplicate-skipping guard. It works regardless of the original order because it does not rely on adjacent elements being equal. Two copies of 7 at positions 2 and 3 will both be encountered when scanning from some start index. The first 7 gets added to the set and explored. When you reach the second 7, the set already contains 7, so you skip it. This prevents duplicate subtrees at the same recursion level without requiring sorted input.
The non-decreasing constraint is enforced by a simple check: only extend the current subsequence with a value that is greater than or equal to the last element in it. If nums[i] is less than current[-1], skip that element entirely.
The solution
def findSubsequences(nums: list[int]) -> list[list[int]]:
result = []
def backtrack(start, current):
if len(current) >= 2:
result.append(current[:])
used = set()
for i in range(start, len(nums)):
if nums[i] in used:
continue
if current and nums[i] < current[-1]:
continue
used.add(nums[i])
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
The outer function initializes an empty result list and calls backtrack(0, []). There is no sorting step, which is the first thing that distinguishes this from Subsets II or Combination Sum II.
Inside backtrack, the first thing you do is check whether the current subsequence has length two or more. If it does, you record it. Unlike Subsets where every partial result (including the empty set) is valid, here you only collect subsequences with at least two elements.
Next, you create a fresh used set. This set is local to the current recursion level. It tracks which values (not indices) you have already tried branching on at this level. This is the key deduplication mechanism.
The for loop scans from start to the end of nums. Two guards appear before the choose step. First, if nums[i] is already in used, skip it - you have already explored a branch starting with this value at this level. Second, if current is non-empty and nums[i] is less than current[-1], skip it - adding this element would break the non-decreasing property.
After both guards pass, you add nums[i] to used, append it to current (choose), recurse with i + 1 (explore), and pop it off (unchoose). Passing i + 1 ensures you only consider elements that appear later in the original array, maintaining subsequence order.
Step 1: Start with empty subsequence. Scan nums = [4, 6, 7, 7] from index 0.
No sorting (we must preserve original order). Create a fresh used set for this recursion level. Try 4 at index 0.
Step 2: Pick 4. Recurse from index 1. Pick 6. Now len >= 2, record [4, 6].
6 >= 4, so it extends the non-decreasing property. len = 2, so we record [4, 6]. Continue deeper.
Step 3: Pick 7 at index 2. Record [4, 6, 7]. Then pick 7 at index 3. Record [4, 6, 7, 7].
Both 7s extend the subsequence. After [4,6,7,7], we backtrack. Back at [4,6], index 3 has value 7 but 7 is already in the used set for this level. Skip it.
Step 4: Backtrack to [4]. Pick 7 at index 2. Record [4, 7]. Pick 7 at index 3. Record [4, 7, 7].
7 >= 4, valid. After recording [4,7,7], back at [4] index 3 has value 7 but 7 is already in the used set. Skip.
Step 5: Backtrack to root. Pick 6 at index 1. Then pick 7 at index 2. Record [6, 7].
6 starts a new branch. 7 >= 6, valid. Pick 7 at index 3 next to get [6,7,7].
Step 6: Record [6, 7, 7]. Backtrack to [6], skip dup 7. Then try [7] from root.
Under [6], index 3 has 7 but 7 is already used at that level - skip. Back at root, pick 7 at index 2. Then 7 at index 3 gives [7,7]. At root level, index 3 has 7 but 7 is already in the used set - skip. Done.
Step 7: Final result - 8 non-decreasing subsequences found.
All subsequences have length >= 2 and are non-decreasing. No duplicates because the per-level used set prevented picking the same value twice at any single recursion level.
The walkthrough shows how the per-level set catches duplicate branches. In Step 3, after exploring the first 7 at index 2 under [4, 6], the algorithm encounters the second 7 at index 3. Because 7 is already in the used set for that level, it skips it. The same thing happens at every level where duplicate values appear. This guarantees unique results without sorting.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Backtracking with per-level set | O(n * 2^n) | O(n * 2^n) |
Time is O(n * 2^n) in the worst case. When all elements are unique and sorted in non-decreasing order, every subsequence of length two or more is valid. There can be up to 2^n subsequences, and copying each one takes O(n). The per-level set operations (insert and lookup) are O(1) each and do not change the asymptotic bound.
Space is O(n * 2^n) for storing the result. The recursion stack uses O(n) depth. Each level of the recursion also creates a set that can hold up to n values, but since the stack depth is at most n, the total set space across all active frames is O(n^2), which is dominated by the output size.
The building blocks
This problem combines two reusable patterns that show up across many backtracking problems.
Choose-explore-unchoose backtracking
The same skeleton from Subsets, Combination Sum, and Permutations:
def backtrack(state):
if is_solution(state):
record(state)
for choice in candidates(state):
make_choice(choice)
backtrack(state)
undo_choice(choice)
Here, make_choice is current.append(nums[i]), undo_choice is current.pop(), and is_solution checks len(current) >= 2. The candidate filtering combines the non-decreasing check with the deduplication set.
Per-level set deduplication
When you cannot sort the input (because order matters), use a set at each recursion level to prevent branching on the same value twice:
used = set()
for i in range(start, len(nums)):
if nums[i] in used:
continue
used.add(nums[i])
This is an alternative to the sorted i > start and nums[i] == nums[i - 1] guard. Both techniques prevent the same value from being chosen twice at one recursion level, but the set-based approach works with unsorted input. The trade-off is a small amount of extra space per recursion frame.
The sorted duplicate-skipping guard from Subsets II and Combination Sum II and the per-level set approach here solve the same fundamental problem: preventing duplicate branches at the same recursion level. Choose the sorted guard when you can sort the input. Choose the set when order must be preserved.
Edge cases to watch for
- All identical elements:
nums = [5, 5, 5, 5]. The only valid subsequences are[5, 5],[5, 5, 5], and[5, 5, 5, 5]. The per-level set ensures you do not produce multiple copies of each. - Strictly decreasing input:
nums = [4, 3, 2, 1]. No non-decreasing subsequence of length two or more exists. The result should be an empty list. - All unique and sorted:
nums = [1, 2, 3, 4]. Every possible subsequence of length two or more is valid. This is the worst case for output size. - Length two input:
nums = [1, 1]. Should return[[1, 1]]. The minimum input that produces a result. - Mixed duplicates and order:
nums = [4, 7, 6, 7]. Despite 7 appearing before and after 6, valid subsequences include[4, 7],[4, 6, 7],[4, 7, 7],[6, 7], and[7, 7]. The per-level set correctly handles non-adjacent duplicates.
From understanding to recall
You now see how per-level set deduplication works and why sorting is not an option for subsequence problems. The logic is clear when you read through it. But can you write the solution from scratch under interview pressure?
The details matter. Forgetting to create a fresh used set inside the loop body (instead of outside it) would cause incorrect deduplication across levels. Checking nums[i] < current[-1] without first verifying that current is non-empty would crash. Recording results only at leaves instead of at every node with length two or more would miss valid subsequences. These are not conceptual gaps - they are recall failures.
Spaced repetition closes this gap. You practice writing the backtracking skeleton and the per-level set guard from memory at increasing intervals. After a few rounds, the pattern becomes automatic. You see "non-decreasing subsequences" and the code flows out without hesitation. The per-level set pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems.
Related posts
- Subsets II - Uses sorted duplicate skipping instead of a per-level set. Compare the two deduplication strategies side by side.
- Combination Sum II - Another backtracking problem with duplicate-skipping, but adds a target-sum constraint and early pruning.
- Subsets - The base case with all unique elements and no deduplication needed. Start here if the backtracking skeleton is unfamiliar.