Brackets all over problem

#1

https://ide.codingblocks.com/s/280490 Please tell why I am getting wrong answer using recursive solution.

#2

Okay I will check your code for errors. Know that this is a variation of the balanced parentheses problem.

#3

Yeah, please check and suggest necessary corrections.

#4

Hi I have found two errors in your code:-

  • You have not taken the mod of the answer in your prblem, leading to different answer.

  • Also , 2 of your recursion calls are redundant, ) + s and s + ( as they lead to violation of constraints.

Hint : If the number of the solutions is so large that you need to take modulo 10^9 + 7, will recurion really be able to give all the possible solutions without hitting stack overflow?

#5

I know we need to take modulo and recursion will result into stackoverflow.

But at first, I am applying recursion so as to check if my algo is correct or not and then I will convert this recursive solution to dp one.

Also, my code is not giving correct output even for small cases where taking modulo will not affect the results like -
4 2
((

So i request you to please tell how to get correct output for small cases.

Also I can’t understand the statement

“Also , 2 of your recursion calls are redundant, ) + s and s + ( as they lead to violation of constraints.”

#6

Look at the constraints given :-

  1. At any index, number of opening brackets should be greater than closing brackets
  2. No. of opening and closing brackets should be equal.
    your string s is already balanced. You have to find the number of ways to add two strings a and b such that both the constraints are satisfied. But when you call “) + s” you are breaking constraint 1 of having more opening brackets than closing at any point. Similarly for the “s + (” call.
#7

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.