# Count Number of Special Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-number-of-special-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-special-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
A sequence is **special** if it consists of a **positive** number of `0`s, followed by a **positive** number of `1`s, then a **positive** number of `2`s.

* For example, `[0,1,2]` and `[0,0,1,1,1,2]` are special.
* In contrast, `[2,1,0]`, `[1]`, and `[0,1,2,0]` are not special.

Given an array `nums` (consisting of **only** integers `0`, `1`, and `2`), return _the **number of different subsequences** that are special_. Since the answer may be very large, **return it modulo** `109 + 7`.

A **subsequence** of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Two subsequences are **different** if the **set of indices** chosen are different.

**Example 1:**

**Input:** nums = [0,1,2,2]
**Output:** 3
**Explanation:** The special subsequences are bolded [**0**,**1**,**2**,2], [**0**,**1**,2,**2**], and [**0**,**1**,**2**,**2**].

**Example 2:**

**Input:** nums = [2,2,0,0]
**Output:** 0
**Explanation:** There are no special subsequences in [2,2,0,0].

**Example 3:**

**Input:** nums = [0,1,2,0,1,2]
**Output:** 7
**Explanation:** The special subsequences are bolded:
- [**0**,**1**,**2**,0,1,2]
- [**0**,**1**,2,0,1,**2**]
- [**0**,**1**,**2**,0,1,**2**]
- [**0**,**1**,2,0,**1**,**2**]
- [**0**,1,2,**0**,**1**,**2**]
- [**0**,1,2,0,**1**,**2**]
- [0,1,2,**0**,**1**,**2**]

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 2`

# Approaches
## Brute-Force Backtracking
This approach involves generating every possible subsequence of the input array `nums`. For each subsequence generated, a check is performed to determine if it qualifies as a "special" subsequence. A counter is used to tally the total number of such special subsequences found.
**Time:** O(N * 2^N). There are 2^N subsequences to generate. For each subsequence, the `isSpecial()` check can take up to O(N) time. · **Space:** O(N), where N is the length of `nums`. This is due to the recursion depth and the space required to store the current subsequence being built.
**Pros:** Conceptually simple and directly follows the problem's definition of a subsequence.; Easy to implement for someone familiar with recursion and backtracking.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
### Explanation
The core of this method is a backtracking algorithm. We can define a recursive function that explores two choices for each element in the input array: either include it in the current subsequence or not. This process branches out, eventually generating all 2^N possible subsequences, where N is the length of `nums`.

When the recursion reaches the end of the array, we have a complete subsequence. We then pass this subsequence to a validation function, `isSpecial()`. This function checks if the subsequence adheres to the required structure: a non-empty sequence of 0s, followed by a non-empty sequence of 1s, and finally a non-empty sequence of 2s. If the subsequence is valid, we increment our total count. Because two subsequences are different if their chosen indices are different, this method correctly counts all valid combinations. However, its exponential nature makes it impractical for the given constraints.
### Algorithm
- Define a recursive function, say `findSubsequences(index, currentList)`, to generate all subsequences.
- The `index` parameter tracks the current position in the `nums` array, and `currentList` stores the subsequence being built.
- **Base Case**: When `index` reaches the end of `nums`, check if `currentList` is a special subsequence using a helper function `isSpecial()`.
- If `isSpecial()` returns true, increment a global counter (modulo `10^9 + 7`).
- **Recursive Step**: For each element at `index`, make two recursive calls:
  1. One without including `nums[index]` in `currentList`.
  2. One including `nums[index]` in `currentList`.
- The `isSpecial(list)` helper function verifies if a given list follows the `0...1...2...` pattern with at least one of each number.

## Dynamic Programming with O(N) Space
A more efficient method is to use dynamic programming. We can build the solution iteratively by keeping track of the number of valid subsequences of different types as we scan through the input array. This avoids the redundant calculations inherent in the brute-force approach.
**Time:** O(N), as we iterate through the input array once with constant time operations at each step. · **Space:** O(N), for the DP table of size `(N+1) x 3`.
**Pros:** Provides a correct and efficient polynomial-time solution (O(N)).; The DP state transitions are logical and easy to follow.
**Cons:** Uses O(N) space, which is not optimal for this problem.; Can be memory-intensive for very large N, although it fits within typical constraints.
### Explanation
We define a DP table, `dp[i][j]`, to store counts up to index `i-1` of the input array. The second dimension `j` represents the type of subsequence we are counting:
- `j=0`: Subsequences with only 0s (e.g., `[0]`, `[0,0]`).
- `j=1`: Subsequences with 0s followed by 1s (e.g., `[0,1]`, `[0,0,1,1]`).
- `j=2`: Special subsequences with 0s, then 1s, then 2s.

We iterate through `nums`, and for each element `nums[i-1]`, we calculate `dp[i]` based on `dp[i-1]`. The logic is that for each number, we can either not include it (in which case the counts are the same as `dp[i-1]`) or include it. If we include `nums[i-1]`, it can extend existing subsequences or start new ones, and we update the corresponding count. For example, if we see a `1`, it can extend any subsequence of type 0 or type 1. The total count for type 1 subsequences at step `i` will be the sum of subsequences from `i-1` plus the new ones we can form. The final answer is the total count of type 2 subsequences after processing the entire array.
### Algorithm
- Create a 2D DP table `dp[n+1][3]`, where `n` is the length of `nums`.
- `dp[i][0]` will store the count of subsequences using `nums[0...i-1]` of the form `0...`.
- `dp[i][1]` will store the count of subsequences using `nums[0...i-1]` of the form `0...1...`.
- `dp[i][2]` will store the count of subsequences using `nums[0...i-1]` of the form `0...1...2...` (special subsequences).
- Iterate `i` from 1 to `n`. In each iteration, first copy the results from the previous step: `dp[i][j] = dp[i-1][j]`.
- Then, update the counts based on the current number `nums[i-1]`:
  - If `nums[i-1] == 0`: Update `dp[i][0] = (dp[i][0] + dp[i-1][0] + 1) % MOD`.
  - If `nums[i-1] == 1`: Update `dp[i][1] = (dp[i][1] + dp[i-1][0] + dp[i-1][1]) % MOD`.
  - If `nums[i-1] == 2`: Update `dp[i][2] = (dp[i][2] + dp[i-1][1] + dp[i-1][2]) % MOD`.
- The final answer is `dp[n][2]`.

## Space-Optimized Dynamic Programming
This is the most optimal solution. It improves upon the previous DP approach by reducing the space complexity. By observing that the DP calculation at step `i` only requires the results from step `i-1`, we can eliminate the need for a full DP table and use only a few variables to store the necessary state.
**Time:** O(N), as it involves a single pass through the input array. · **Space:** O(1), as we only use a constant number of variables to maintain the counts.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Highly efficient and scalable for large inputs.
**Cons:** The logic for the state transitions, while concise, might be slightly less intuitive to derive compared to the table-based approach.
### Explanation
Instead of a 2D array, we use three variables: `count0`, `count1`, and `count2`, to represent the number of subsequences ending in 0, 1, and 2, respectively, that satisfy the special sequence prefix rules. We iterate through the input array `nums` once.

- When we encounter a `0`: Any new subsequence ending with this `0` can be formed by either appending it to an existing subsequence of `0`s (doubling the possibilities, hence `2 * count0`) or by starting a new subsequence with this single `0` (adding 1). So, `count0` becomes `(2 * count0 + 1) % MOD`.
- When we encounter a `1`: A new subsequence ending with this `1` can be formed by appending it to any subsequence ending in `0` (`count0` ways) or any subsequence ending in `1` (`count1` ways). The total count becomes `count1` (old ones) + `count0` + `count1` (new ones), which simplifies to `count1 = (2 * count1 + count0) % MOD`.
- When we encounter a `2`: Following the same logic, a new subsequence ending in `2` can be formed by appending it to any subsequence ending in `1` (`count1` ways) or `2` (`count2` ways). Thus, `count2 = (2 * count2 + count1) % MOD`.

After iterating through all numbers, `count2` contains the total count of special subsequences.
### Algorithm
- Initialize three `long` variables: `count0`, `count1`, `count2` to 0.
- `count0`: stores the number of valid subsequences ending in 0.
- `count1`: stores the number of valid subsequences ending in 1 (of form `0...1...`).
- `count2`: stores the number of valid special subsequences (of form `0...1...2...`).
- Iterate through each `num` in the `nums` array.
- Based on the value of `num`, update the counts using the following recurrence relations (all operations are modulo `10^9 + 7`):
  - If `num == 0`: `count0 = (2 * count0 + 1)`.
  - If `num == 1`: `count1 = (2 * count1 + count0)`.
  - If `num == 2`: `count2 = (2 * count2 + count1)`.
- After the loop finishes, `count2` will hold the final answer.

# Solutions
### Java

```java
class Solution {
public
  int countSpecialSubsequences(int[] nums) {
    final int mod = (int)1 e9 + 7;
    int n = nums.length;
    int[][] f = new int[n][3];
    f[0][0] = nums[0] == 0 ? 1 : 0;
    for (int i = 1; i < n; ++i) {
      if (nums[i] == 0) {
        f[i][0] = (2 * f[i - 1][0] % mod + 1) % mod;
        f[i][1] = f[i - 1][1];
        f[i][2] = f[i - 1][2];
      } else if (nums[i] == 1) {
        f[i][0] = f[i - 1][0];
        f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1] % mod) % mod;
        f[i][2] = f[i - 1][2];
      } else {
        f[i][0] = f[i - 1][0];
        f[i][1] = f[i - 1][1];
        f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2] % mod) % mod;
      }
    }
    return f[n - 1][2];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countSpecialSubsequences(vector<int> &nums) {
    const int mod = 1e9 + 7;
    int n = nums.size();
    int f[n][3];
    memset(f, 0, sizeof(f));
    f[0][0] = nums[0] == 0;
    for (int i = 1; i < n; ++i) {
      if (nums[i] == 0) {
        f[i][0] = (2 * f[i - 1][0] % mod + 1) % mod;
        f[i][1] = f[i - 1][1];
        f[i][2] = f[i - 1][2];
      } else if (nums[i] == 1) {
        f[i][0] = f[i - 1][0];
        f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1] % mod) % mod;
        f[i][2] = f[i - 1][2];
      } else {
        f[i][0] = f[i - 1][0];
        f[i][1] = f[i - 1][1];
        f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2] % mod) % mod;
      }
    }
    return f[n - 1][2];
  }
};

```

### Python

```python
class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 n = len(nums) f = [[0] * 3 for _ in range(n)] f[0][0] = nums[0] == 0 for i in range(1, n): if nums[i] == 0: f[i][0] = (2 * f[i - 1][0] + 1) % mod f[i][1] = f[i - 1][1] f[i][2] = f[i - 1][2] elif nums[i] == 1: f[i][0] = f[i - 1][0] f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1]) % mod f[i][2] = f[i - 1][2] else: f[i][0] = f[i - 1][0] f[i][1] = f[i - 1][1] f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2]) % mod return f[n - 1][2]

```