**We need to find out the number of ways we can form a N-length array(A) consisting only 3 elements (1,2 and 3).**

There are few constraints on how array's **adjacent elements** can be placed in the array:

Number of adjacent elements pairs `(A[i], A[i + 1])` of a certain type cannot exceed as given in the problem statement.

```
example :

1, 2 : 2 (we can have at most 2 adjacent-pairs of value [1, 2] in the array)
1, 3 : 3
2, 1 : 1
2, 3 : 0 (we cannot have any adjacent-pairs of value [2, 3] in entire array)
3, 1 : 4
3, 2 : 3

```

**For adjacent elements of type** `A[i] == A[i + 1]`, they can be any number of times in the array

```
1, 1 : inf
2, 2 : inf
3, 3 : inf

```

**Sample Case :**

> 
> ***Input*** :
> 
> 
> 

```
N = 3

1, 2 : 1 
1, 3 : 1
2, 1 : 1
2, 3 : 0 
3, 1 : 0
3, 2 : 0   

```

> 
> ***Output :***
> 
> 
> 

```
12

```

> 
> ***Explanation :***
> 
> 
> 

```
[1, 2, 1] , here { (1,2) : 1, (2,1) : 1 }, so valid 
[1, 2, 2]
[1, 1, 2]
[2, 1, 2]

[1, 3, 3] , here { (1,3) : 1, (3,3) : 1 }, so valid 
[1, 1, 3]
[2, 1, 3] , here { (2,1) : 1, (1,3) : 1 }, so valid 

[2, 1, 1] , here { (2,1) : 1, (1,1) : 1 }, so valid 
[2, 2, 1]     

[1, 1, 1] , here { (1,1) : 2 }, so valid, as adj-pairs (x, x) can be any number of times.
[2, 2, 2]
[3, 3, 3]

All other combinations of 1,2,3 are invalid like :
[3, 1, 1], [2, 3, 1], etc.

```

> 
> **Constraints**
> 
> 
> 

```
1 <= N <= 10^6

0 <= limit[i][j] <= 10^5

where N = array length and limit[i][j] = number of pairs of type (i, j)

```

> 
> **Pseudocode :**
> 
> 
> 

```
main() :
   ways = 0;
   for(p = 1; p <= 3; p++) :
       ways += num_ways(p, 1, n, A, limit);
   return ways;

num_ways(prev, i, n, A[], limit[][]) :

  if(i == n) return 1;

  ways = 0;
  for(e = 1; e <= 3; e++):
      if(limit[prev][e] > 0) 
          limit[prev][e] -= 1;
          ways += num_ways(e, i + 1, A, limit);
          limit[prev][e] += 1;

  return ways;

, where limit[i][j] means max number of adjacent-pairs of value (i, j) that can be present in array

```

**Pseudocode Explanation :**

I tried to solve this using **recursion** (brute-force), i.e at **every function call** insert any element `(1,2,3)` at index `i` and check if `(A[i - 1], A[i])` pair hasn't exceed the limit as per given in problem statement, and if **yes** then `return` else **continue calling** `func()` while `i != n`.

This approach is fine, but it's giving TLE(time limit exceeded) error, hence it's not the most optimal way to find out number of ways to form array.

> 
> **Is there any other efficient way to solve this problem ?**
> 
> 
>