Can anyone explain me how to proceed with this problem…
How to proceed with this problem
Hello @soumakpoddar55,
I’ll describe this approach below (with a few minor tweaks).
The recurrence used is f(i, j) which returns the number of valid bracket sequences from position 1 to i with j more opening brackets than closing brackets. For convenience let’s call the difference between opening and closing brackets simply the difference. If we are at position i and we need j more “[” than “]”, then we can obtain that by two ways.
We put a “[” at position i to get a difference j. This means that there must have been a difference of j-1 upto position i-1.
We put a “]” at position i to get a difference j. This implies that there must have been a difference of j+1 upto position i−1.
We are also given a set of positions s which must contain “[”. For such positions, option 2 is unavailable. For j<0 naturally f(i, j)=0 because we are proceeding from left to right and if we have more “]” than “[” we can never end up with a valid sequence. Again f(0,0)=1 as the empty sequence with difference 0 is valid. Also f(0,j) for j>0 is 0
Putting all of this together,
f(i,j)=
0 if j<0 or i=0,j>0
1 if i=0,j=0
f(i−1,j−1) if i is in s
f(i−1,j−1)+f(i−1,j+1) otherwise
The final answer will be f(2n,0) as 2n is the last position in our sequence and we want the sequence to be valid, so we need difference 0.
you can refer to the solution itself it has nice explanation.
improper bracket expression means int bracket expression which is valid i.e. equal number of opening and closing brackets and makes sense eg
]][[,[[[]],][][,[[[[[ etc
Hope, this would help.