Skip to main content

Generate Parentheses

Question​

None

Example 1
Result: (()())

Solution​

all//Generate Parentheses.py


def generateParenthesis(n):
    # list to store the generated parenthesis
    ans = []

    # Calling the recursive helper
    # function to generate all parentheses
    backtrack(ans, "", 0, 0, n)
    return ans

# Function to generate all valid
# parentheses combinations
def backtrack(ans, cur, open, close, max):

    # If the length of the current
    # resultant string has reached 2*max
    if len(cur) == 2 * max:
        ans.append(cur)
        return

    # If open bracket count is less than
    # the maximum number of brackets
    if open < max:
        backtrack(ans, cur + "(", open + 1, close, max)

    # If close bracket count is less
    # than open bracket count
    if close < open:
        backtrack(ans, cur + ")", open, close + 1, max)

# Driver code
n = 3
print(generateParenthesis(n))

# Output: ['((()))', '(()())', '(())()', '()(())', '()()()']