# 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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Output | All distinct non-decreasing subsequences |
| Minimum length | At least `2` |
| Order rule | Keep original index order |
| Duplicate rule | Return each value sequence only once |

Function shape:

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

## Examples

Example 1:

```python
nums = [4, 6, 7, 7]
```

Valid subsequences include:

```python
[4, 6]
[4, 6, 7]
[4, 6, 7, 7]
[4, 7]
[4, 7, 7]
[6, 7]
[6, 7, 7]
[7, 7]
```

Answer:

```python
[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
```

Example 2:

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

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

```python
[4, 4]
```

Answer:

```python
[[4, 4]]
```

## First Thought: Generate Every Subsequence

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

For every element, we choose either:

| Choice | Meaning |
|---|---|
| Take it | Add it to the current subsequence |
| Skip it | Move past it |

That gives at most:

```text
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:

```python
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:

```python
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 `7`s 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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * 2^n)` | There can be exponentially many subsequences, and copying each path costs up to `O(n)` |
| Space | `O(n)` excluding output | Recursion depth and current path are at most `n` |

The output itself may also contain exponentially many subsequences.

## Implementation

```python
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:

```python
ans = []
```

The current subsequence is stored in:

```python
path = []
```

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

```python
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:

```python
used = set()
```

This skips repeated values that would create the same branch:

```python
if nums[i] in used:
    continue
```

This keeps the subsequence non-decreasing:

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

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

```python
dfs(i + 1)
```

Then we undo the choice:

```python
path.pop()
```

## Testing

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

```python
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:

| Test | Why |
|---|---|
| `[4, 6, 7, 7]` | Main example with duplicates |
| `[4, 4, 3, 2, 1]` | Only one duplicate-based answer |
| `[1, 2, 3]` | Fully increasing array |
| `[3, 2, 1]` | No valid length-two non-decreasing subsequence |
| `[1, 1, 1]` | Repeated equal values without duplicate outputs |