No test case apssing

#1

I checked with many sample etst cases.
Tried on hackerblocks for submitting but it is not submitting.

#2

@piyush.bansal8158625
Hello piyush,
ur logic for generating all paranthesis is correct but it is not printing in required order.

#3

How will I get to know which order is required. It only depeneds on how we are inputting string

I tried for sample case 2 as (()) and ()() also…both failed

#4

@piyush.bansal8158625
store strings in descending order. for that pass greater as second argument while declaring ur set

#5

Getting TLE for first 4 cases cases.last one passed

#6

@piyush.bansal8158625
because time complexity is (n+1)!*log(n)

other solution is to construct string 2*n length string by either placing ( or ) .and then store in vector or set if it is balanced.
its time complexity will be 2^n *n which is less than previous soultion

#7

I didn’t get that hint. 1st how is my time complexity calculated
2nd How to create string without permutations part…Is balancing using stack is correct.?

#8

@piyush.bansal8158625
your approach and solution is 100 % correct. it is just taking more time.

see n+1! factorial is to generate total number of permutations and for each permutaion we run isvalid function which is O(n) and log(n) to insert in set.
so n! * n * log(n) which is roughly (n+1)! * log(n)

#9

Thats correct .

Now How to change time complexity.
either permutattion part/balanced pair check/insertion in set check

which of the 3 needs to be updated and how

#10

@piyush.bansal8158625

u need to change ur permuation part.

we will generate string starting from empty string.

start from empty string construct a string of 2n length ( which will contain ( or ) )
how ->
write a recusrive function for each postion place ( then go to next position or place ) then go to next postion
when hit base case (i.e position equal to 2n) check whether the generated string is valid or not. if valid then insert in set.

#11

Not generating any output for n>3. If any mistake in recursion or any line please comment it

#12

@piyush.bansal8158625
change ur c string to c++ string datatype with size 2*n

#13

Please make the changes. I am not getting output for my changes.

#14
#15

Thanks passed all test case…If possible please solve rat in a maze doubt tagged with you…2 test cases are failing in it

#16

@piyush.bansal8158625
pls dont forget to mark ur doubt as resolved