# Non-decreasing Subsequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/non-decreasing-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/non-decreasing-subsequences
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
---
## Problem
Given an integer array `nums`, return _all the different possible non-decreasing subsequences of the given array with at least two elements_. You may return the answer in **any order**.

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

**Constraints:**

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

# Approaches
## Brute Force: Generate and Filter
This approach generates every possible subsequence of the input array. Then, it filters these subsequences based on two criteria: they must be non-decreasing, and they must have a length of at least two. To handle duplicate subsequences that might be formed, a `Set` is used to store the valid ones, ensuring uniqueness.
**Time:** O(n * 2^n). We iterate through `2^n` potential subsequences. For each, building the subsequence takes O(n) time, and validating it also takes O(n). Adding a list of size `k` to a hash set takes O(k) time. Thus, the overall complexity is dominated by this exponential factor. · **Space:** O(n * 2^n). In the worst-case scenario (e.g., a sorted array of unique elements), the `resultSet` might need to store a number of subsequences on the order of `2^n`, with each subsequence having a length up to `n`.
**Pros:** Conceptually simple and straightforward to implement.; Guaranteed to find all valid subsequences.
**Cons:** Extremely inefficient due to its O(n * 2^n) time complexity, making it unsuitable for `n` larger than about 20.; Generates a vast number of subsequences that are immediately discarded, wasting computation.; High space complexity to store all generated subsequences before filtering and then storing the results.
### Explanation
The core of this method is to iterate through all `2^n` subsets of the given array `nums`. We can achieve this using bit manipulation, where each integer from `1` to `2^n - 1` represents a bitmask. If the `j`-th bit in the mask is `1`, it signifies that the `j`-th element of `nums` is included in the current subsequence.

For each generated subsequence, we perform two checks:
1.  **Size Check:** The subsequence must contain at least two elements.
2.  **Non-decreasing Check:** We iterate through the subsequence to ensure that each element is greater than or equal to the one preceding it.

If a subsequence satisfies both conditions, it is added to a `Set<List<Integer>>`. Using a `Set` conveniently handles the problem of duplicate subsequences, as a `Set` only stores unique elements. Finally, the contents of the `Set` are transferred to a `List` to match the required return type.

```java
class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        Set<List<Integer>> resultSet = new HashSet<>();
        int n = nums.length;
        for (int i = 1; i < (1 << n); i++) {
            List<Integer> subsequence = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    subsequence.add(nums[j]);
                }
            }
            if (subsequence.size() >= 2) {
                boolean isNonDecreasing = true;
                for (int k = 1; k < subsequence.size(); k++) {
                    if (subsequence.get(k) < subsequence.get(k - 1)) {
                        isNonDecreasing = false;
                        break;
                    }
                }
                if (isNonDecreasing) {
                    resultSet.add(subsequence);
                }
            }
        }
        return new ArrayList<>(resultSet);
    }
}
```
### Algorithm
- Create a `Set<List<Integer>> resultSet` to store unique valid subsequences.
- Get the length `n` of the input array `nums`.
- Iterate through all possible non-empty subsets using a bitmask `i` from `1` to `(1 << n) - 1`.
- For each bitmask `i`, construct the corresponding subsequence:
  - Create an empty `List<Integer> subsequence`.
  - Iterate from `j = 0` to `n - 1`. If the `j`-th bit of `i` is set, add `nums[j]` to `subsequence`.
- After constructing the `subsequence`, validate it:
  - If `subsequence.size() < 2`, discard it.
  - Check if the subsequence is non-decreasing. Iterate from the second element and ensure `subsequence[k] >= subsequence[k-1]`.
  - If it is valid, add it to the `resultSet`.
- Finally, convert the `resultSet` to a `List` and return it.

## Backtracking with Result Set
This approach uses recursion (backtracking) to build the non-decreasing subsequences more intelligently. Instead of generating every subsequence and then filtering, we only extend the current subsequence with elements that maintain the non-decreasing property. A `Set` is still used for the final result to automatically handle duplicates that might arise from identical numbers in the input array (e.g., in `[4, 7, 7]`, `[4, 7]` can be formed in two ways).
**Time:** O(n * 2^n). The recursion tree can have up to `2^n` nodes. At each valid terminal node, we add a list to the set, which takes O(n) for hashing. While better than brute-force, the complexity remains exponential. · **Space:** O(n * 2^n). The recursion depth is O(n). The main space is consumed by the `result` set, which can store up to O(2^n) subsequences, each of length up to O(n).
**Pros:** More efficient than the brute-force approach because it prunes branches that would lead to non-decreasingly sorted subsequences.; The logic directly maps to the problem of building sequences incrementally.
**Cons:** Relies on a `Set` to handle duplicates, which involves hashing entire lists. This can be less performant than preventing duplicate generation in the first place.; It explores redundant recursive paths when the input array contains duplicate numbers, leading to unnecessary computations.
### Explanation
A recursive helper function, say `backtrack(index, currentList)`, forms the foundation of this method. The `index` parameter indicates the starting position in the `nums` array from which to select the next element, and `currentList` holds the subsequence constructed so far.

The recursion proceeds as follows:
1.  First, we check if the `currentList` has at least two elements. If so, it's a valid result, and we add a copy of it to a global `Set<List<Integer>>`.
2.  Next, we loop from the current `index` to the end of the `nums` array. For each element `nums[i]`, we check if adding it to `currentList` would maintain the non-decreasing order. This is true if `currentList` is empty or if `nums[i]` is greater than or equal to the last element in `currentList`.
3.  If `nums[i]` is a valid candidate, we add it to `currentList` and make a recursive call for the rest of the array: `backtrack(i + 1, currentList)`.
4.  Upon returning from the recursive call, we remove `nums[i]` from `currentList`. This backtracking step is crucial as it allows us to explore other subsequences that don't include `nums[i]` at this position.

```java
class Solution {
    private Set<List<Integer>> result;
    private int[] nums;

    public List<List<Integer>> findSubsequences(int[] nums) {
        this.result = new HashSet<>();
        this.nums = nums;
        backtrack(0, new ArrayList<>());
        return new ArrayList<>(result);
    }

    private void backtrack(int index, List<Integer> current) {
        if (current.size() >= 2) {
            result.add(new ArrayList<>(current));
        }

        for (int i = index; i < nums.length; i++) {
            if (current.isEmpty() || nums[i] >= current.get(current.size() - 1)) {
                current.add(nums[i]);
                backtrack(i + 1, current);
                current.remove(current.size() - 1);
            }
        }
    }
}
```
### Algorithm
- Initialize a `Set<List<Integer>> result` to store the final unique subsequences.
- Define a recursive helper function, `backtrack(index, currentList)`.
- The `index` parameter tracks the current position in the `nums` array, and `currentList` is the subsequence being built.
- In the `backtrack` function:
  - If `currentList.size() >= 2`, it's a valid subsequence, so add a copy of it to the `result` set.
  - Iterate through `nums` from `i = index` to the end.
  - For each element `nums[i]`, check if it can extend the current subsequence: `currentList` must be empty, or `nums[i]` must be greater than or equal to the last element of `currentList`.
  - If the condition is met, add `nums[i]` to `currentList` and make a recursive call: `backtrack(i + 1, currentList)`.
  - After the recursive call returns, remove `nums[i]` from `currentList` to backtrack and explore other possibilities.
- Start the process by calling `backtrack(0, new ArrayList<>())`.
- Return a `List` created from the `result` set.

## Optimized Backtracking with Level-wise Deduplication
This is the most efficient approach, building upon the backtracking method. It cleverly avoids generating duplicate subsequences from the start, which eliminates the need for a final `Set` for deduplication. The key is to track which numbers have already been used at the current level of the recursion, thereby pruning the search space.
**Time:** O(n * 2^n). While the worst-case complexity is the same (for an array with unique, sorted elements), this approach is much faster in practice for inputs with duplicates because it prunes large parts of the recursion tree. The work per node is dominated by list copying (O(n)). · **Space:** O(n * 2^n). The space is dominated by the `result` list. The recursion stack uses O(n) space, and each `usedInThisLevel` set uses at most O(k) space where k is the number of unique elements in the range `[-100, 100]`, which is constant in this problem.
**Pros:** Most efficient solution by preventing duplicate work, making it significantly faster for inputs with repeated numbers.; Avoids the overhead of using a `Set` for the final results and hashing lists.; Directly builds the final, unique list of subsequences.
**Cons:** The logic is slightly more complex due to the need to manage the `usedInThisLevel` set at each step of the recursion.; The worst-case time and space complexity are still exponential, which is inherent to the problem of finding all subsequences.
### Explanation
This optimized backtracking approach refines the previous one by handling duplicates during the recursive construction itself. The main recursive function `backtrack(index, currentList)` remains, but with an added mechanism for deduplication.

Inside each call to `backtrack`, we introduce a local `Set<Integer>` called `usedInThisLevel`. This set's purpose is to keep track of the numbers we have already chosen to extend the subsequence *at the current decision point*. 

When we iterate from `i = index` to the end of the array, for each element `nums[i]`, we first check if it maintains the non-decreasing property. If it does, we then check if `nums[i]` is already in `usedInThisLevel`. If it is, it means we have already explored all possible subsequences starting with the current prefix followed by `nums[i]`. For example, if the prefix is `[4]` and the remaining array is `[..., 7, ..., 7]`, once we process the first `7`, we add it to `usedInThisLevel` and won't process the second `7` for the same prefix `[4]`. This effectively prunes the search tree and prevents duplicate subsequences from ever being generated.

```java
class Solution {
    private List<List<Integer>> result;
    private int[] nums;

    public List<List<Integer>> findSubsequences(int[] nums) {
        this.result = new ArrayList<>();
        this.nums = nums;
        backtrack(0, new ArrayList<>());
        return result;
    }

    private void backtrack(int index, List<Integer> current) {
        if (current.size() >= 2) {
            result.add(new ArrayList<>(current));
        }
        
        // This set tracks numbers used at the current level of recursion
        // to avoid duplicate subsequences.
        Set<Integer> usedInThisLevel = new HashSet<>();
        
        for (int i = index; i < nums.length; i++) {
            // Maintain non-decreasing order
            if (current.isEmpty() || nums[i] >= current.get(current.size() - 1)) {
                // Skip if the current number has been used at this level
                if (usedInThisLevel.contains(nums[i])) {
                    continue;
                }
                
                usedInThisLevel.add(nums[i]);
                current.add(nums[i]);
                backtrack(i + 1, current);
                current.remove(current.size() - 1);
            }
        }
    }
}
```
### Algorithm
- Initialize a `List<List<Integer>> result`.
- Define a recursive helper function `backtrack(index, currentList)`.
- In the `backtrack` function:
  - If `currentList.size() >= 2`, add a copy to the `result` list.
  - To prevent duplicates at the current level of recursion, initialize a local `Set<Integer> usedInThisLevel`.
  - Iterate through `nums` from `i = index` to the end.
  - For each element `nums[i]`, apply two checks:
    1.  **Non-decreasing check:** `currentList` must be empty or `nums[i]` must be `>=` the last element of `currentList`.
    2.  **Duplicate check:** The number `nums[i]` must not have been used at this specific recursive depth yet. Check this using `!usedInThisLevel.contains(nums[i])`.
  - If both checks pass:
    - Mark `nums[i]` as used for this level: `usedInThisLevel.add(nums[i])`.
    - Add `nums[i]` to `currentList`.
    - Make the recursive call: `backtrack(i + 1, currentList)`.
    - Backtrack by removing `nums[i]` from `currentList`.
- Start the process by calling `backtrack(0, new ArrayList<>())`.
- Return the `result` list.

# Solutions
### Java

```java
class Solution {
private
  int[] nums;
private
  List<List<Integer>> ans;
public
  List<List<Integer>> findSubsequences(int[] nums) {
    this.nums = nums;
    ans = new ArrayList<>();
    dfs(0, -1000, new ArrayList<>());
    return ans;
  }
private
  void dfs(int u, int last, List<Integer> t) {
    if (u == nums.length) {
      if (t.size() > 1) {
        ans.add(new ArrayList<>(t));
      }
      return;
    }
    if (nums[u] >= last) {
      t.add(nums[u]);
      dfs(u + 1, nums[u], t);
      t.remove(t.size() - 1);
    }
    if (nums[u] != last) {
      dfs(u + 1, last, t);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> findSubsequences(vector<int> &nums) {
    vector<vector<int>> ans;
    vector<int> t;
    dfs(0, -1000, t, nums, ans);
    return ans;
  }
  void dfs(int u, int last, vector<int> &t, vector<int> &nums,
           vector<vector<int>> &ans) {
    if (u == nums.size()) {
      if (t.size() > 1)
        ans.push_back(t);
      return;
    }
    if (nums[u] >= last) {
      t.push_back(nums[u]);
      dfs(u + 1, nums[u], t, nums, ans);
      t.pop_back();
    }
    if (nums[u] != last)
      dfs(u + 1, last, t, nums, ans);
  }
};

```

### Python

```python
class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]: def dfs(u, last, t): if u == len(nums): if len(t) > 1: ans . append(t[:]) return if nums[u] >= last: t . append(nums[u]) dfs(u + 1, nums[u], t) t . pop() if nums[u] != last: dfs(u + 1, last, t) ans = [] dfs(0, - 1000, []) return ans

```