LeetCode 491: Non-decreasing Subsequences Solution in Python – A Step-by-Step Guide

What Is LeetCode 491: Non-decreasing Subsequences?

In LeetCode 491: Non-decreasing Subsequences, you’re given an integer array nums, and your task is to return all unique non-decreasing subsequences with at least two elements. A subsequence is non-decreasing if each element is greater than or equal to the previous one (e.g., [4, 6], [4, 7]), and duplicates must be avoided in the result. For example, with nums = [4, 6, 7, 7], valid subsequences include [[4,6], [4,7], [6,7], [7,7], [4,6,7], [4,7,7]], totaling 6 unique sequences. It’s like sifting through an array to find every ascending path that’s at least two steps long, ensuring no repeats muddy the list.

Problem Statement

• Input: nums (List[int])—array of integers.
• Output: List[List[int]]—all unique non-decreasing subsequences with length ≥ 2.
• Rules:
• Subsequence: pick elements in order, not necessarily contiguous.
• Non-decreasing: each element ≥ previous.
• Length ≥ 2.
• Return unique subsequences only.

Constraints

• \( 1 \leq nums.length \leq 15 \).
• \( -100 \leq nums[i] \leq 100 \).

Examples to Get Us Started

• Input: nums = [4,6,7,7]
• Output: [[4,6],[4,7],[6,7],[7,7],[4,6,7],[4,7,7]] (6 unique sequences).
• Input: nums = [4,4,3,2,1]
• Output: [[4,4]] (Only one valid sequence).
• Input: nums = [1,2,3]
• Output: [[1,2],[1,3],[2,3],[1,2,3]].

Understanding the Problem: Uncovering the Paths

To solve LeetCode 491: Non-decreasing Subsequences in Python, we need to find all subsequences of nums that are non-decreasing and at least two elements long, ensuring no duplicates in the result. A naive approach—generating all subsequences and filtering—could be O(2^n), slow for n = 15, with additional deduplication overhead. The key? Use DFS with a set to build sequences incrementally, pruning non-increasing paths and avoiding duplicates efficiently. We’ll explore:

• Best Solution (DFS with Set-Based Deduplication): O(2^n) time, O(2^n) space—fast and optimal for this problem.
• Alternative Solution (Brute Force Subsequence Generation): O(2^n) time, O(2^n) space—simple but less efficient.

Let’s dive into the DFS solution—it’s the sleuth’s clever magnifying glass we need.

Best Solution: DFS with Set-Based Deduplication

Why This Is the Best Solution

The DFS with set-based deduplication is the top pick because it’s O(2^n) time (n = array length) and O(2^n) space, efficiently finding all unique non-decreasing subsequences by using depth-first search to build sequences incrementally, pruning paths that violate the non-decreasing rule, and using a set to eliminate duplicates without excessive overhead. It balances speed and memory, leveraging Python’s set for fast lookups. It’s like tracing every ascending path through the array, jotting down unique finds as you go—smart and streamlined!

How It Works

Here’s the strategy:

• Step 1: Initialize:
• Result list to store subsequences.
• Set to track unique sequences (as tuples for hashability).
• Step 2: DFS function:
• Parameters: index (current position), current subsequence (curr).
• Base: if len(curr) ≥ 2, add to result if unique.
• Recurse: for each i from index to end:
• Skip if curr not empty and nums[i] < last element.
• Include nums[i], recurse, backtrack.
• Step 3: Start DFS from index 0, empty curr.
• Step 4: Return result list.
• Why It Works:
• DFS builds all subsequences, pruning non-increasing ones.
• Set ensures uniqueness in O(1) lookup time.

Step-by-Step Example

Example: nums = [4,6,7,7]

• Init: result = [], seen = set().
• DFS(0, []):
• \( DFS(0, [4]) \):
• \( DFS(1, [4,6]) \): Add [4,6], seen = {(4,6)}.
• \( DFS(2, [4,7]) \): Add [4,7], seen = {(4,6), (4,7)}.
• \( DFS(3, [4,7]) \): Add [4,7] (duplicate), skip.
• \( DFS(1, [4,6,7]) \): Add [4,6,7], seen = {(4,6), (4,7), (4,6,7)}.
• \( DFS(1, [6]) \):
• \( DFS(2, [6,7]) \): Add [6,7], seen = {(4,6), (4,7), (4,6,7), (6,7)}.
• \( DFS(2, [7]) \):
• \( DFS(3, [7,7]) \): Add [7,7], seen = {(4,6), (4,7), (4,6,7), (6,7), (7,7)}.
• Result: [[4,6], [4,7], [6,7], [7,7], [4,6,7], [4,7,7]] (order may vary).

Example: nums = [4,4,3]

• DFS(0, []):
• \( DFS(0, [4]) \):
• \( DFS(1, [4,4]) \): Add [4,4].
• \( DFS(1, [4]) \): No further increase.
• Result: [[4,4]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        # Step 1: Initialize
        result = []
        seen = set()

        def dfs(index: int, curr: List[int]):
            # Step 2: Base case - add if length >= 2 and unique
            if len(curr) >= 2:
                curr_tuple = tuple(curr)
                if curr_tuple not in seen:
                    seen.add(curr_tuple)
                    result.append(curr[:])

            # Recurse from index
            for i in range(index, len(nums)):
                # Prune if not non-decreasing
                if not curr or nums[i] >= curr[-1]:
                    curr.append(nums[i])
                    dfs(i + 1, curr)
                    curr.pop()

        # Step 3: Start DFS
        dfs(0, [])

        # Step 4: Return result
        return result

• Line 4-5: Init result list and seen set for deduplication.
• Line 7-18: DFS:
• If curr ≥ 2, add to result if unseen (as tuple for set).
• For each i from index:
• Skip if violates non-decreasing.
• Add nums[i], recurse, backtrack.
• Line 21: Start DFS with empty curr.
• Line 24: Return result.
• Time Complexity: O(2^n)—explores all subsequences.
• Space Complexity: O(2^n)—stores unique subsequences.

It’s like a sequence-tracing sleuth!

Alternative Solution: Brute Force Subsequence Generation

Why an Alternative Approach?

The brute force subsequence generation—O(2^n) time, O(2^n) space—generates all possible subsequences using bitmasks, filters for non-decreasing and length ≥ 2, then deduplicates. It’s slow and memory-heavy but intuitive, like sifting every possible path by hand. Good for small arrays or learning!

How It Works

• Step 1: Generate all subsequences (2^n via bitmask).
• Step 2: Filter:
• Length ≥ 2.
• Non-decreasing.
• Step 3: Deduplicate with set.
• Step 4: Return result list.

Step-by-Step Example

Example: nums = [4,6]

• Masks: 00, 01, 10, 11.
• 01: [6].
• 10: [4].
• 11: [4,6] (non-decreasing, ≥ 2).
• Result: [[4,6]].

Code for Brute Force

Copy codeclass Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        def is_non_decreasing(seq):
            for i in range(1, len(seq)):
                if seq[i] < seq[i-1]:
                    return False
            return True

        n = len(nums)
        result = set()
        # Step 1: Generate all subsequences
        for mask in range(1 << n):
            seq = []
            for i in range(n):
                if mask & (1 << i):
                    seq.append(nums[i])
            # Step 2: Filter
            if len(seq) >= 2 and is_non_decreasing(seq):
                result.add(tuple(seq))

        # Step 3-4: Convert to list and return
        return [list(seq) for seq in result]

• Line 3-7: Check if sequence is non-decreasing.
• Line 10-18: Generate, filter, deduplicate.
• Line 21: Convert set to list.
• Time Complexity: O(2^n)—all subsequences.
• Space Complexity: O(2^n)—stores subsequences.

It’s a slow sequence sifter!

Comparing the Two Solutions

• DFS with Deduplication (Best):
• Pros: O(2^n), efficient, prunes early.
• Cons: O(2^n) space.
• Brute Force (Alternative):
• Pros: O(2^n), straightforward.
• Cons: No pruning, less efficient.

DFS wins for optimization.

Edge Cases and Examples

• Input: [1] → [] (no length ≥ 2).
• Input: [1,1] → [[1,1]].
• Input: [3,2,1] → [] (no increasing pairs).

DFS handles all perfectly.

Complexity Recap

• DFS: Time O(2^n), Space O(2^n).
• Brute Force: Time O(2^n), Space O(2^n).

DFS is the champ for pruning.

Key Takeaways

• DFS: Build smartly.
• Brute Force: Generate all.
• Python Tip: Sets dedupe—see [Python Basics](/python/basics).

Final Thoughts: Sleuth Those Sequences

LeetCode 491: Non-decreasing Subsequences in Python is a sequence-hunting adventure. DFS with deduplication is your fast sleuth, while brute force is a slow digger. Want more sequence challenges? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 491: Non-decreasing Subsequences. Ready to find some paths? Head to Solve LeetCode 491 on LeetCode and sleuth it today—your coding skills are sequence-ready!