Like traversaling a binary three with O(n^2) nodes


  • 5
    R
    (root 0,0) -->-->-->-->
                 |  |  |  |
                  -->-->-->
                    |  |  |
                     -->-->
                       |  | 
                        -->
                          |
                              (leaf n,n)
    

    At each point of the sequence, the number of "(" is no less than that of ")". So all possible states are nodes in the above figure. forward means adding a "(", and downward means adding a ")". Thus, there is a binary tree! with each node represented by a coordinate.

    For n pairs, there are (n+2)(n+1)/2 = O(n^2). Can be


  • 0
    Z
    This post is deleted!

  • 0
    V

    It's not a 'binary tree'. It's a half directional grid with 'forward' and 'downward' edges.

    The number of valid permutations is equivalent to half the number of paths from left-highest node to right-lowest node.
    The number of paths is A = number of combinations to choose n from 2n
    = (2n)! / (n! * n!) = (1+1/n)(1+2/n)(1+3/n)...(1+n/n)
    This number A: A > e^n and A<2^n. But it's still exponential.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.