Skip to main content
Talentd

Non-decreasing Subsequences - Solution & Explanation

MediumArrayHash TableBacktrackingBit Manipulation7 min readAsked at: Amazon, Google, Yahoo
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Recursive Backtracking

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative with Bitmasking

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`.

Code

JavaScriptJava

JavaScript

Java

Complexity

Time Complexity: O(n * 2^n) due to checking each subsequence for validity.

Space Complexity: O(n * 2^n) for storing all subsequences.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Backtracking with SetO(2^n)O(n)Best general solution. Efficient duplicate pruning and commonly expected in interviews.
Iterative Bitmask EnumerationO(n * 2^n)O(n)Good for understanding subset generation or when implementing iterative solutions.

Video Solution

Non-decreasing Subsequences | Khaandani Backtracking Template | Explanation | Live Coding • codestorywithMIK • 19,435 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Non-decreasing Subsequences easy or hard?
Non-decreasing Subsequences is considered a medium-level problem. Generating subsequences is straightforward, but handling duplicates while preserving order introduces additional complexity. The difficulty mainly comes from managing recursion state and pruning duplicate branches efficiently.
How to solve Non-decreasing Subsequences in O(n)?
An O(n) algorithm is not possible because the number of valid subsequences can grow exponentially with the input size. Any correct algorithm must potentially enumerate up to 2^n subsequences. Efficient solutions focus on pruning invalid branches early using backtracking and hash sets to avoid generating duplicates.
What is the best approach for Non-decreasing Subsequences?
Recursive backtracking with a per-level hash set is the most efficient and commonly accepted solution. The algorithm builds subsequences incrementally while ensuring each next value keeps the sequence non-decreasing. A set at each recursion depth prevents duplicate subsequences when the input array contains repeated numbers. The overall complexity is O(2^n) time with O(n) recursion space.
Is Non-decreasing Subsequences asked at Google/Amazon/Meta?
Non-decreasing subsequence generation problems appear in interviews at companies like Amazon, Meta, and Google as variations of backtracking and subset generation. The problem tests recursion, duplicate pruning, and sequence validation—skills commonly evaluated in medium-level algorithm interviews.
What data structure is used in Non-decreasing Subsequences?
The main data structures include arrays for traversal, recursion stacks for backtracking, and hash sets to prevent duplicate subsequences. The set is typically used at each recursion level to ensure the same value is not chosen multiple times from the same depth of the search tree.
What is the time complexity of Non-decreasing Subsequences?
The typical backtracking solution runs in O(2^n) time because each element can either be included or skipped when generating subsequences. Additional checks ensure the subsequence remains non-decreasing and duplicates are avoided. Space complexity is O(n) for the recursion stack, excluding the space required to store resulting subsequences.
Non-decreasing Subsequences Python or Java solution approach?
Python and Java implementations usually rely on recursive backtracking. The algorithm maintains a current path list, checks if the next number keeps the sequence non-decreasing, and uses a set at each recursion depth to skip duplicates. JavaScript and Java variants sometimes demonstrate a bitmask enumeration approach as an alternative.

Ready to solve this problem?

Practice Non-decreasing Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Length of Pair Chain