Information Technology

Backtracking Algorithms: Generate Parentheses

This series of articles covers a set of popular computer science problems. 

The problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

 

Solution:

    def generateParenthesis(n):
        result = []
        
        def bt(opened, closed, curr):
            if closed == n:
                result.append(''.join(curr))
                return
            if opened < n:
                curr.append('(')
                bt(opened + 1, closed, curr)
                curr.pop()
            if closed < opened:
                curr.append(')')
                bt(opened, closed + 1, curr)
                curr.pop()
        bt(0, 0, [])
        return result