Generate Parentheses | DSA Journal

Question

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Example

Input: n = 3

Output: ["()()()", "()(())", "(())()", "(()())", "((()))"]

Explanation: All valid combinations of three pairs of balanced parentheses are listed above.

My Notes

Use a stack to explore all possible combinations using DFS (depth-first search).
Each node on the stack stores:
- val: current string of parentheses
- o: number of open brackets used
- c: number of close brackets used
If o < n: we can add an open bracket → push ( to stack.
If c < o: we can add a close bracket → push ) to stack.
If the string length is 2 * n, it’s complete → add to result.

package main

import (
    "fmt"
)

type Node struct {
    val string
    o   int
    c   int
}

type Stack struct {
    items []Node
}

func (s *Stack) Push(val string, o int, c int) {
    s.items = append(s.items, Node{val, o, c})
}

func (s *Stack) Pop() Node {
    popped := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return popped
}

func (s *Stack) IsEmpty() bool {
    return len(s.items) == 0
}

func generateParenthesis(n int) []string {
    result := []string{}
    stack := Stack{items: []Node{{val: "", o: 0, c: 0}}}
    
    for !stack.IsEmpty() {
        node := stack.Pop()

        if node.o < n {
            stack.Push(node.val+"(", node.o+1, node.c)
        }

        if node.c < node.o {
            stack.Push(node.val+")", node.o, node.c+1)
        }

        if len(node.val) == 2*n {
            result = append(result, node.val)
        }
    }

    return result
}

func main() {
    result := generateParenthesis(3)
    fmt.Println(result)
}