LeetCode 491: Non-decreasing Subsequences

Problem Restatement

We are given an integer array nums.

We need to return all different non-decreasing subsequences with length at least 2.

A subsequence keeps the original order, but may skip elements.

A sequence is non-decreasing if every next value is greater than or equal to the previous value.

The answer can be returned in any order. The constraints are 1 <= nums.length <= 15 and -100 <= nums[i] <= 100.

Input and Output

Function shape:

def findSubsequences(nums: list[int]) -> list[list[int]]:
    ...

Examples

Example 1:

nums = [4, 6, 7, 7]

Valid subsequences include:

[4, 6]
[4, 6, 7]
[4, 6, 7, 7]
[4, 7]
[4, 7, 7]
[6, 7]
[6, 7, 7]
[7, 7]

Answer:

[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

Example 2:

nums = [4, 4, 3, 2, 1]

The only valid non-decreasing subsequence of length at least two is:

[4, 4]

Answer:

[[4, 4]]

First Thought: Generate Every Subsequence

Since nums.length <= 15, we can think about generating subsequences.

For every element, we choose either:

That gives at most:

2^n

subsequences.

After generating one, we can check whether it is non-decreasing and has length at least 2.

This works, but duplicate values cause duplicate subsequences.

For example:

nums = [4, 6, 7, 7]

The subsequence [4, 7] can be created by choosing the first 7 or the second 7.

We need a cleaner way to avoid duplicates while building.

Key Insight

Use backtracking.

At each recursion level, we choose the next element to append to the current path.

To keep the path non-decreasing, we may append nums[i] only when:

not path or nums[i] >= path[-1]

To avoid duplicates, use a local set at each recursion level.

The local set records which values have already been chosen as the next value from this exact position.

For example, if two 7s are available at the same recursion level, we should only start one branch with 7.

This removes duplicate subsequences without blocking valid repeated values like [7, 7].

Algorithm

Define a DFS function:

dfs(start)

where start is the first index we are allowed to consider.

Maintain a list path.

Inside dfs(start):

1. If len(path) >= 2, add a copy of path to the answer.
2. Create an empty set used.
3. For each index i from start to the end:
   • Skip nums[i] if it was already used at this recursion level.
   • Skip nums[i] if it would make path decreasing.
   • Otherwise, append nums[i].
   • Recurse with dfs(i + 1).
   • Pop it from path.

Correctness

The DFS builds subsequences in increasing index order because after choosing index i, the next recursive call starts at i + 1. Therefore, every generated sequence is a valid subsequence of nums.

The condition:

not path or nums[i] >= path[-1]

ensures every appended value is at least the previous value. Therefore, every generated path is non-decreasing.

Whenever the path length is at least 2, the algorithm adds it to the answer, so every generated valid subsequence is recorded.

Now consider any valid non-decreasing subsequence. Its indices appear in increasing order. At each step, the DFS can choose the next required index because the value satisfies the non-decreasing condition. Therefore, the DFS reaches that subsequence and records it.

The used set at each recursion level prevents two branches from choosing the same value as the next element from the same start position. Those branches would produce duplicate value sequences. Since it only blocks duplicate choices at the same depth, it still allows the same value to appear again later in the path, such as [7, 7].

Thus the algorithm returns exactly all distinct non-decreasing subsequences of length at least 2.

Complexity

The output itself may also contain exponentially many subsequences.

Implementation

class Solution:
    def findSubsequences(self, nums: list[int]) -> list[list[int]]:
        ans = []
        path = []

        def dfs(start: int) -> None:
            if len(path) >= 2:
                ans.append(path[:])

            used = set()

            for i in range(start, len(nums)):
                if nums[i] in used:
                    continue

                if path and nums[i] < path[-1]:
                    continue

                used.add(nums[i])
                path.append(nums[i])

                dfs(i + 1)

                path.pop()

        dfs(0)
        return ans

Code Explanation

The result list stores all valid subsequences:

ans = []

The current subsequence is stored in:

path = []

When the current path has length at least two, it is a valid answer:

if len(path) >= 2:
    ans.append(path[:])

We copy with path[:] because path will keep changing during backtracking.

The local set prevents duplicate choices at this recursion depth:

used = set()

This skips repeated values that would create the same branch:

if nums[i] in used:
    continue

This keeps the subsequence non-decreasing:

if path and nums[i] < path[-1]:
    continue

After choosing a value, we recurse only into later indices:

dfs(i + 1)

Then we undo the choice:

path.pop()

Testing

Since the answer may be returned in any order, normalize before comparing.

def normalize(items):
    return sorted(tuple(x) for x in items)

def run_tests():
    s = Solution()

    assert normalize(s.findSubsequences([4, 6, 7, 7])) == normalize([
        [4, 6],
        [4, 6, 7],
        [4, 6, 7, 7],
        [4, 7],
        [4, 7, 7],
        [6, 7],
        [6, 7, 7],
        [7, 7],
    ])

    assert normalize(s.findSubsequences([4, 4, 3, 2, 1])) == normalize([
        [4, 4],
    ])

    assert normalize(s.findSubsequences([1, 2, 3])) == normalize([
        [1, 2],
        [1, 2, 3],
        [1, 3],
        [2, 3],
    ])

    assert normalize(s.findSubsequences([3, 2, 1])) == []
    assert normalize(s.findSubsequences([1, 1, 1])) == normalize([
        [1, 1],
        [1, 1, 1],
    ])

    print("all tests passed")

run_tests()

Test meaning: