In a topcoder problem recently, there was this definition:
Correct parentheses sequences can be defined recursively as follows:
* The empty string "" is a correct sequence.
* If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
* If "X" is a correct sequence, then "(X)" is a correct sequence.
* Each correct parentheses sequence can be derived using the above rules.
What is the purpose of the last line?
I've seen this type of extra condition many times and have to spend time thinking about whether it means something for the solution. Usually I can't think of something, and so (for me) it wastes time during a contest.
This just means there are no other bracket sequences: all bracket sequences that exist can be generated this way.
Suppose we deleted that last line. Is there some bracket sequence that does not fit the first three conditions? Thanks.
Any sequence, like
())))(. If that sentence wasn't there, then that might also be a correct bracket sequence, because there's nothing explicitly saying it isn't.