unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 22: Generate Parentheses

link

Valid parentheses have two criteria:

  1. We can include “(” if one is available.
  2. We cannot close more than opens. So, we include “)” only if enough opens have already been included.

Recursive

Time: \mathcal{O}(2^{2\cdot n} \cdot n), space: \mathcal{O}(n).

class Solution:
    def collect(self, n, open_count, close_count, curr, parens):
        if len(curr) == 2*n:
            parens.append( "".join(curr) )
            return
        
        if open_count < n:
            curr.append("(")
            self.collect(n, open_count+1, close_count, curr, parens)
            curr.pop()
        
        if close_count < open_count:
            curr.append(")")
            self.collect(n, open_count, close_count+1, curr, parens)
            curr.pop()

    def generateParenthesis(self, n: int) -> List[str]:
        # ( ( (  
        # ) ) )
        parens = []
        self.collect(n, 0, 0, [], parens)

        return parens

tanvirdotzaman

,

Leave a comment