Recursion problem : Class assignment

#1

my code is working correctly to generate the combinations of string according to conditions but i have to output the number of combinations and i am using global variable (ambiguity problem)…please help

#2

hi @mandeepchohan96 you dont have to actually generate all the strings, 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)
Can you figure out the base cases?

1 Like
#3

i had written this code acc to your instructions but it is showing wrong…mam,can you correct my code ?

#4

@mandeepchohan96 your code is correct, it may be showing TLE because time complexity of recursion is very high. So you will need to use memoization along with recursion.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.