How can i solve by backtracking?

#1

how can i solve it by using backtracking?

#2

you can easily make a recurrance relation to find the number of integers.

you have to make an n-digit number.
so for the ith digit, you have 2 options.

  1. You can place ai at ith place. If you do this, you can place either ai or bi at i+1th place, it does not matter. So subproblem becomes for f(n-1)
  2. You can place bi at the ith place, If you do this, you can place only ai at i+1th place, because you cant have bi next to next. So the subproblem becomes for f(n-2)

The recurrance relation becomes f(n) = f(n-1) + f(n-2)