Non-decreasing Subsequences solution and explanation
Google
9 more videos on this problem
Non-decreasing Subsequences | Khaandani Backtracking Template | Explanation | Live CodingcodestorywithMIK · 29:42 · 19K views
LeetCode 491 Non Decreasing SubsequenceJeevan Kumar - Cracckify · 7:54 · 3K views
491. Non-decreasing Subsequences | LeetCodeDeep Tech · 12:45 · 2K views
Leetcode 491. Non-decreasing Subsequences | CodingDecoded SDE sheetCoding Decoded · 5:49 · 1K views
Leetcode 491: Non-decreasing SubsequencesAlgorithms Casts · 12:39 · 1K views
Non-decreasing Subsequences | Leetcode - 491 | Python | Coding InterviewTechError · 7:26 · 969 views
Leetcode 491 Non-decreasing Subsequences (Java)TheAnalyticGuy · 9:33 · 557 views
Leetcode 491: Non-decreasing Subsequences | Master Backtracking | Intuition and ApproachCode Concepts with Animesh · 25:03 · 515 views
491. Non-decreasing Subsequences | Backtracking + Bit Manipulation | LeetCode MediumJust enjoy the journey · 25:05 · 455 views
491. Non-decreasing Subsequences - LEETCODECode Crusaders · 8:00 · 329 views
The problem
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.
from typing import List
def findSubsequences(nums: List[int]) -> List[List[int]]:
def backtrack(start, path):
if len(path) > 1:
res.add(tuple(path))
for i in range(start, len(nums)):
if not path or path[-1] <= nums[i]:
backtrack(i + 1, path + [nums[i]])
res = set()
backtrack(0, [])
return [list(seq) for seq in res]
# Example usage
nums = [4,6,7,7]
print(findSubsequences(nums))#include <vector>
#include <set>
using namespace std;
void backtrack(int start, vector<int>& nums, vector<int>& path, set<vector<int>>& res) {
if (path.size() > 1) {
res.insert(path);
}
for (int i = start; i < nums.size(); ++i) {
if (path.empty() || path.back() <= nums[i]) {
path.push_back(nums[i]);
backtrack(i + 1, nums, path, res);
path.pop_back();
}
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
set<vector<int>> res;
vector<int> path;
backtrack(0, nums, path, res);
return vector<vector<int>>(res.begin(), res.end());
}
// Example usage
// vector<int> nums = {4,6,7,7};
// vector<vector<int>> result = findSubsequences(nums);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.
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.
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.
import java.util.*;
public class Solution {
public List<List<Integer>> findSubsequences(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
int n = nums.length;
for (int mask = 1; mask < (1 << n); mask++) {
List<Integer> sequence = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
if (sequence.isEmpty() || sequence.get(sequence.size() - 1) <= nums[i]) {
sequence.add(nums[i]);
} else {
sequence.clear();
break;
}
}
}
if (sequence.size() > 1) {
result.add(sequence);
}
}
return new ArrayList<>(result);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {4,6,7,7};
System.out.println(sol.findSubsequences(nums));
}
}var findSubsequences = function(nums) {
const result = new Set();
const n = nums.length;
for (let mask = 1; mask < (1 << n); mask++) {
const sequence = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
if (!sequence.length || sequence[sequence.length - 1] <= nums[i]) {
sequence.push(nums[i]);
} else {
break;
}
}
}
if (sequence.length > 1) {
result.add(sequence.toString());
}
}
return Array.from(result).map(seq => seq.split(",").map(Number));
};
// Example usage
// console.log(findSubsequences([4,6,7,7]));The Java implementation uses bitmasking to generate subsequences, with a `HashSet` to handle duplicates. Each bit in the mask corresponds to an element, and their presence in each subsequence is determined iteratively. Valid subsequences are added to the result after ensuring the non-decreasing order.
Time Complexity: O(n * 2^n) for generating and checking subsequences.
Space Complexity: O(n * 2^n) due to the result storage.
Approach 3: Default Approach
func findSubsequences(nums []int) [][]int {
var ans [][]int
var dfs func(u, last int, t []int)
dfs = func(u, last int, t []int) {
if u == len(nums) {
if len(t) > 1 {
ans = append(ans, slices.Clone(t))
}
return
}
if nums[u] >= last {
t = append(t, nums[u])
dfs(u+1, nums[u], t)
t = t[:len(t)-1]
}
if nums[u] != last {
dfs(u+1, last, t)
}
}
var t []int
dfs(0, -1000, t)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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) for generating and checking subsequences. Space Complexity: O(n * 2^n) due to the result storage. |
| Default Approach | – |
Complexity analysis
| 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. |
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.