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

$ curl repovive.com/roadmaps/fundamental-algorithms/backtracking/generate-parentheses

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

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

$ curl repovive.com/roadmaps/fundamental-algorithms/backtracking/generate-parentheses

Repovive

Generate Parentheses - Backtracking | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Generate Parentheses

Generate all valid parentheses combinations.

Problem: Generate all strings of $n$ pairs of balanced parentheses.

Approach: Track open and close counts. Add '(' if open < n. Add ')' if close < open.

function backtrack(n, open, close, current, result):
    if current.length == 2 * n:
        result.add(current)
        return
    if open < n:
        backtrack(n, open + 1, close, current + "(", result)
    if close < open:
        backtrack(n, open, close + 1, current + ")", result)

Count: Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ .