Problem Description

You are given an integer array nums. Your task is to find all possible subsequences that satisfy two conditions:

1. The subsequence must be non-decreasing (each element is greater than or equal to the previous one)
2. The subsequence must contain at least two elements

A subsequence is formed by deleting some (possibly zero) elements from the original array without changing the relative order of the remaining elements. For example, [1,3] is a subsequence of [1,2,3].

The key challenge is that you need to return all different possible non-decreasing subsequences, meaning no duplicates should appear in your result. The subsequences can be returned in any order.

For example:

• If nums = [4,6,7,7], the valid non-decreasing subsequences with at least 2 elements would include: [4,6], [4,6,7], [4,6,7,7], [4,7], [4,7,7], [6,7], [6,7,7], and [7,7].

The solution uses a depth-first search (DFS) approach with backtracking. The algorithm explores each position in the array and makes two choices at each step:

1. Include the current element if it's greater than or equal to the last selected element
2. Skip the current element (but only if it's different from the last value to avoid duplicates)

The variable last tracks the value of the previously selected element (initialized to -1000 to handle all valid integer inputs), and t maintains the current subsequence being built. When the end of the array is reached and the subsequence has at least 2 elements, it's added to the answer list.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves finding subsequences in an array, not traversing nodes and edges in a graph structure.

Need to solve for kth smallest/largest?

• No: We need to find all valid subsequences, not the kth smallest or largest element.

Involves Linked Lists?

• No: The problem works with an integer array, not linked list nodes.

Does the problem have small constraints?

• Yes: Finding all possible subsequences is inherently exponential (2^n possibilities), which typically means the problem has small constraints to be computationally feasible. Each element can either be included or excluded, leading to exploring all combinations.

Brute force / Backtracking?

• Yes: We need to explore all possible subsequences systematically. Backtracking is perfect here because:
  • We build subsequences incrementally
  • We need to explore multiple paths (include or skip each element)
  • We can prune invalid paths (when elements would break the non-decreasing property)
  • We need to track and backtrack our choices to explore all possibilities

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This aligns perfectly with the solution, which uses DFS with backtracking to explore all valid non-decreasing subsequences by making decisions at each index (include if valid, or skip) and backtracking to explore alternative paths.

Intuition

When we need to find all possible subsequences with certain properties, we're essentially exploring a decision tree. At each position in the array, we face a choice: include this element or skip it. This naturally leads to a backtracking approach.

Think of building subsequences like making a series of choices. Starting from the first element, we can either:

1. Take it (if it maintains the non-decreasing property)
2. Leave it

After making a choice, we move to the next element and repeat. This creates a tree of decisions where each path from root to leaf represents a different subsequence.

The key insight for avoiding duplicates is subtle but important. Consider [4, 6, 7, 7]. If we're at index 2 (first 7) and our current subsequence is [4, 6], we can:

• Add 7 to get [4, 6, 7] and continue exploring
• Skip this 7 and move to the next position

But when we reach index 3 (second 7), if we already skipped a 7 at index 2, we shouldn't explore skipping again - it would generate the same subsequences we already found. This is why the code checks if nums[u] != last before recursing without adding the current element.

The last parameter serves dual purpose:

1. It ensures we maintain the non-decreasing property (only add elements >= last)
2. It helps avoid duplicate subsequences by preventing redundant "skip" operations for equal consecutive values

By systematically exploring all valid paths in this decision tree and collecting subsequences with at least 2 elements, we guarantee finding all unique non-decreasing subsequences.

Solution Approach

The solution implements a depth-first search (DFS) with backtracking to explore all possible subsequences. Here's how the implementation works:

Core DFS Function Structure:

The dfs(u, last, t) function takes three parameters:

• u: Current index in the array we're considering
• last: The value of the last element added to our subsequence (or -1000 initially)
• t: The current subsequence being built

Base Case: When u == len(nums), we've considered all elements. If our subsequence t has at least 2 elements, we add a copy to our answer list.

Recursive Cases:

At each position, we make up to two recursive calls:

1. Include current element (if valid):

   if nums[u] >= last:
       t.append(nums[u])
       dfs(u + 1, nums[u], t)
       t.pop()  # backtrack

   We can only include nums[u] if it maintains the non-decreasing property (nums[u] >= last). After exploring this path, we backtrack by removing the element.

2. Skip current element (with duplicate avoidance):

   if nums[u] != last:
       dfs(u + 1, last, t)

   We skip the current element, but only if it's different from last. This crucial check prevents generating duplicate subsequences when we have repeated values.

Why the duplicate check works:

Consider when nums[u] == last. This means we just added a value equal to nums[u] in the previous step. If we skip nums[u] now, we'd be exploring subsequences that don't include this value - but we already explored those paths when we decided not to include the previous occurrence. So we avoid this redundant exploration.

Data Structures:

• ans: List to store all valid subsequences
• t: Temporary list used during DFS to build subsequences (modified and restored via backtracking)

Initial Call: dfs(0, -1000, []) starts at index 0, with -1000 as the initial last value (chosen to be smaller than any valid array element), and an empty subsequence.

The algorithm has time complexity of O(2^n * n) in the worst case (where we might generate up to 2^n subsequences, each taking O(n) to copy), and space complexity of O(n) for the recursion stack and temporary subsequence storage.

Example Walkthrough

Let's trace through the algorithm with nums = [4, 6, 7, 7].

We start with dfs(0, -1000, []) - at index 0, last value is -1000, empty subsequence.

At index 0 (value = 4):

• Since 4 >= -1000, we can include 4: Add 4 to subsequence → [4], recurse with dfs(1, 4, [4])

  At index 1 (value = 6), subsequence = [4]:

  • Since 6 >= 4, include 6: [4,6] → dfs(2, 6, [4,6])

    At index 2 (value = 7), subsequence = [4,6]:

    • Since 7 >= 6, include 7: [4,6,7] → dfs(3, 7, [4,6,7])

      At index 3 (value = 7), subsequence = [4,6,7]:

      • Since 7 >= 7, include 7: [4,6,7,7] → dfs(4, 7, [4,6,7,7])
        • Reached end, len([4,6,7,7]) >= 2, add [4,6,7,7] to answer ✓
      • Since 7 == 7 (nums[3] == last), DON'T skip (would be duplicate)

    • Since 7 != 6, skip 7: keep [4,6] → dfs(3, 6, [4,6])

      At index 3 (value = 7), subsequence = [4,6]:

      • Since 7 >= 6, include 7: [4,6,7] → dfs(4, 7, [4,6,7])
        • Reached end, add [4,6,7] to answer ✓
      • Since 7 != 6, skip 7: [4,6] → dfs(4, 6, [4,6])
        • Reached end, add [4,6] to answer ✓

  • Since 6 != 4, skip 6: keep [4] → dfs(2, 4, [4])

    At index 2 (value = 7), subsequence = [4]:

    • Since 7 >= 4, include 7: [4,7] → dfs(3, 7, [4,7])

      At index 3 (value = 7), subsequence = [4,7]:

      • Since 7 >= 7, include 7: [4,7,7] → dfs(4, 7, [4,7,7])
        • Reached end, add [4,7,7] to answer ✓
      • Since 7 == 7, DON'T skip

    • Since 7 != 4, skip 7: [4] → dfs(3, 4, [4])

      At index 3 (value = 7), subsequence = [4]:

      • Since 7 >= 4, include 7: [4,7] → dfs(4, 7, [4,7])
        • Reached end, add [4,7] to answer ✓

• Since 4 != -1000, skip 4: empty subsequence → dfs(1, -1000, [])

  This branch explores subsequences not starting with 4, eventually finding [6,7], [6,7,7], and [7,7].

The key insight: when we have last = 7 and encounter another 7, we don't explore skipping it because we already explored "subsequences without this 7" when we skipped the previous 7.

Final answer: [[4,6,7,7], [4,6,7], [4,6], [4,7,7], [4,7], [6,7,7], [6,7], [7,7]]

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^n * n)

The algorithm explores all possible subsequences using backtracking. At each position u, we have at most 2 choices:

1. Include nums[u] if it's greater than or equal to the last element
2. Skip nums[u] if it's different from the last element

This creates a decision tree with depth n (where n is the length of nums), and at each node we make up to 2 recursive calls. This gives us O(2^n) recursive calls in the worst case.

Additionally, when we find a valid subsequence (length > 1), we copy it to the answer list using t[:], which takes O(n) time in the worst case.

Therefore, the overall time complexity is O(2^n * n).

Space Complexity: O(n)

The space complexity consists of:

1. Recursion call stack: The maximum depth of recursion is n, requiring O(n) space
2. Temporary list t: This stores the current subsequence being built, which can have at most n elements, requiring O(n) space
3. Output space: The ans list stores all valid subsequences (not counted in auxiliary space complexity as it's part of the output)

The auxiliary space complexity is O(n) for the recursion stack and temporary storage.

If we include the output space, there can be up to 2^n subsequences, each of maximum length n, giving a total space complexity of O(2^n * n).

Common Pitfalls

Pitfall 1: Incorrect Duplicate Handling

The Problem: A common mistake is trying to use a set to remove duplicates after generating all subsequences, or checking if a subsequence already exists in the result before adding it:

# INCORRECT approach
def findSubsequences(self, nums):
    result = []
  
    def dfs(index, path):
        if index == len(nums):
            if len(path) > 1 and path not in result:  # Inefficient!
                result.append(path[:])
            return
      
        # Include current element
        if not path or nums[index] >= path[-1]:
            path.append(nums[index])
            dfs(index + 1, path)
            path.pop()
      
        # Always skip (no duplicate check)
        dfs(index + 1, path)
  
    dfs(0, [])
    return result

This generates many duplicate subsequences and checking membership with path not in result is O(n*m) for each check, making the solution extremely inefficient.

The Solution: The key insight is preventing duplicates during generation rather than filtering them afterward. The condition if nums[index] != last_value when skipping ensures we don't explore redundant branches:

# CORRECT approach
if nums[index] != last_value:
    dfs(index + 1, last_value, current_path)

Pitfall 2: Using a Set at Each Recursion Level

The Problem: Another approach people try is using a set at each recursion level to track which values have been used:

# INCORRECT - creates too many set objects
def dfs(index, path):
    if index == len(nums):
        if len(path) > 1:
            result.append(path[:])
        return
  
    used = set()  # New set for each recursion level
    for i in range(index, len(nums)):
        if nums[i] in used:
            continue
        if not path or nums[i] >= path[-1]:
            used.add(nums[i])
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()

While this can work, it's unnecessarily complex and creates many set objects. The elegant solution using last_value comparison achieves the same deduplication with simpler logic.

Pitfall 3: Misunderstanding the Deduplication Logic

The Problem: Some might think the condition should be reversed:

# INCORRECT logic
if nums[index] == last_value:  # Wrong condition!
    dfs(index + 1, last_value, current_path)

This would skip elements when they equal the last value, which is exactly when we DON'T want to skip (because we'd be creating the same subsequence pattern we already explored).

The Solution: Remember the logic: we skip the current element only when nums[index] != last_value. When they're equal, we've just included this value in a previous branch, so skipping it now would recreate subsequences we've already generated when we didn't include the previous occurrence.

Pitfall 4: Incorrect Initial Value for last_value

The Problem: Using an insufficient initial value:

# INCORRECT if array contains -100
dfs(0, -100, [])  # Won't work for nums = [-100, -99]

Since the constraint states -100 <= nums[i] <= 100, using -100 as the initial value would incorrectly prevent -100 from being the first element in a subsequence.

The Solution: Use a value guaranteed to be smaller than any array element:

dfs(0, -1000, [])  # Or float('-inf')