#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/complete-search/generate-parentheses-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/complete-search/generate-parentheses-implementation

Repovive

Generate Parentheses - Implementation - Complete Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Generate Parentheses - Implementation

Here is the implementation:

function generateParenthesis(n):
    result = []
    backtrack("", 0, 0)
    return result

function backtrack(current, open, close):
    if current.length == 2 * n:
        result.append(current)
        return

    if open < n:
        backtrack(current + "(", open + 1, close)

    if close < open:
        backtrack(current + ")", open, close + 1)

The number of valid strings is $C_n = \frac{1}{n+1}\binom{2n}{n}$ . Each string has length $2n$ .