Generate Parentheses

1. Problem Description

The number n represents the number of pairs of parentheses. Design a function that can generate all possible valid combinations of parentheses.

2. Approach

1. Approach 1
   • Full enumeration + stack
   • At each position, either ( or ) can be used
   • After enumeration, validate whether the parentheses are valid using a stack
2. Approach 2
   1. 
   2. Prune based on the remaining left and right parentheses

3. Implementation

3.1. Full Enumeration + Stack

func generateParenthesis(n int) []string {
    res := make([]string, 0)

    path := make([]rune, n*2)
    generateParenthesisDFS(n*2, 0, path, &res)

    return res
}

func generateParenthesisDFS(n int, index int, path []rune, res *[]string) {
    if index == n {
        if isValid(path) {
            *res = append(*res, string(path))
        }
        return
    }

    path[index] = '('
    generateParenthesisDFS(n, index+1, path, res)
    path[index] = ')'
    generateParenthesisDFS(n, index+1, path, res)
    
}

func isValid(runes []rune) bool {
    stack := make([]rune, 0)

    for _, r := range runes {
        if isLeft(r) {
            stack = append(stack, r)
        }else if isRight(r) {
            if len(stack) == 0 {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
}

func isLeft(ch rune) bool {
    return ch == '('
}

func isRight(ch rune) bool {
    return ch == ')'
}

3.2. Prune Left and Right Parentheses

var m = map[rune]rune {
    '(':')',
}


func generateParenthesis(n int) []string {
    res := make([]string, 0)
    path := make([]rune, 2*n)
    dfs(n, n, 0, path, &res)
    return res
}

func dfs(left int, right int, index int, path []rune, res *[]string) {
    if left == 0 && right == 0 {
        str := string(path)
        if isValid(str) {
            *res = append(*res, str)
        }
        return
    }
    
    // left > right is an invalid prefix, so prune it directly
    if (left > right) {
        return
    }

    if left > 0 {
        path[index] = '('
        dfs(left-1, right, index+1, path, res)
    }
    if right > 0 {
        path[index] = ')'
        dfs(left, right-1, index+1, path, res)
    }

}


func isValid(s string) bool {
    stack := make([]rune, 0)
    for _, r := range []rune(s) {
        if isLeft(r) {
            stack = append(stack, r)
        } else if isRight(r){
            if len(stack) > 0 && isMatch(stack[len(stack)-1], r) {
                stack = stack[:len(stack)-1]
                continue
            }
            return false
        } else {
            return false
        }
    }

    return len(stack) == 0
}

func isLeft(r rune) bool {
    return r == '(' 
}

func isRight(r rune) bool {
    return r == ')'
}

func isMatch(left, right rune) bool{
    return m[left] == right
}

4. References

• Backtracking (Depth-First Traversal) + Breadth-First Traversal (Java) - Generate Parentheses - LeetCode