Non-decreasing Subsequences — Medium Problem & Solution

Problem statement

Return every distinct subsequence of nums that has at least two elements and is non-decreasing (each element is at least the one before it). A subsequence keeps the original order but may skip elements; two subsequences that read the same value by value count once, even if they come from different positions.

List the subsequences in lexicographic order: compare value by value from the left; when one is a prefix of the other, the shorter comes first.

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]]

Example 3

Input: nums = [3,-1,3,0]
Output: [[-1,0],[-1,3],[3,3]]

Constraints

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100

How to solve Non-decreasing Subsequences

Generate each distinct value sequence through its earliest-possible embedding: at every step choose a value (not an index), and take that value's first occurrence after the current position. Distinct choices give distinct sequences, so no hash set of results is needed.

Approach

1. dfs(pos, path): if path has at least two elements, record a copy.
2. Scan i from pos + 1 to the end; for each nums[i] that is at least the last value of path (or any value when path is empty), remember its first such index.
3. For each remembered value in increasing order, append it, recurse with pos set to its first index, and remove it.
4. Start with dfs(-1, []).

Why it works

Any non-decreasing value sequence that occurs in nums also occurs when every element is matched as early as possible, and that greedy embedding is unique — so each distinct subsequence is produced exactly once. Recording before extending puts a prefix before its extensions, and increasing candidate order at every depth makes the whole output lexicographic.

Complexity

• Time — O(2^n · n) in the worst case
• Space — O(n) recursion depth besides the output

Pitfalls

• Deduplicate per recursion level (or globally with a set); deduplicating only adjacent equal elements is wrong because the array is not sorted.
• Do not sort nums — the order of the original array defines which subsequences exist.
• Single elements are not answers; record only paths of length ≥ 2.

Reference solution

Python

from typing import List

def findSubsequences(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    out = []
    path = []

    def dfs(pos):
        if len(path) >= 2:
            out.append(path[:])
        first = {}
        for i in range(pos + 1, n):
            if path and nums[i] < path[-1]:
                continue
            if nums[i] not in first:
                first[nums[i]] = i
        for v in sorted(first):
            path.append(v)
            dfs(first[v])
            path.pop()

    dfs(-1)
    return out

JavaScript

var findSubsequences = function(nums) {
    var n = nums.length;
    var out = [];
    var path = [];
    var dfs = function(pos) {
        if (path.length >= 2) out.push(path.slice());
        var first = new Map();
        for (var i = pos + 1; i < n; i++) {
            if (path.length && nums[i] < path[path.length - 1]) continue;
            if (!first.has(nums[i])) first.set(nums[i], i);
        }
        var vals = Array.from(first.keys()).sort(function(a, b) { return a - b; });
        for (var t = 0; t < vals.length; t++) {
            path.push(vals[t]);
            dfs(first.get(vals[t]));
            path.pop();
        }
    };
    dfs(-1);
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium
• Subsets II Medium