LC 0022 [M] Generate Parentheses - ALawliet/algorithms GitHub Wiki

non-graph DFS

"generate all combinations"

---

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def branch(n_left, n_right, path):
            # base case: we used all the parens and it's even for both L and R
            if len(path) == 2*n:
                combinations.append(path)
            else:
                # the most ( we can have is n
                if n_left < n:
                    branch(n_left + 1, n_right, path + '(')

                # we can add ) to close a pair if we opened an L without an R
                if n_left > n_right:
                    branch(n_left, n_right + 1, path + ')')
            
        combinations = []
        branch(0, 0, '')
        return combinations