Generate Parentheses - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Generate Parentheses" Problem in Go

Difficulty: Medium | Tags: String, Dynamic Programming, Backtracking

Introduction

Generating all combinations of well-formed parentheses is a classic problem that tests understanding of recursion and backtracking. It is commonly encountered in technical interviews and competitive programming.

Problem Analysis

Given an integer n, the task is to generate all possible valid combinations of n pairs of parentheses. A combination is valid if every opening parenthesis has a corresponding closing parenthesis. For example, when n = 3, the valid combinations are ["((()))","(()())","(())()","()(())","()()()"].

Solution Approach

The problem can be efficiently solved using backtracking. The idea is to build the combinations incrementally, ensuring at each step that the number of opening parentheses is never less than the number of closing parentheses. We recursively explore all valid paths by adding either an opening or closing parenthesis when the constraints allow it.

Go Implementation


func generateParenthesis(n int) []string {
    var result []string
    backtrack(&result, "", 0, 0, n)
    return result
}
func backtrack(result *[]string, current string, open, close, max int) {
    if len(current) == max*2 {
        *result = append(*result, current)
        return
    }
    if open < max {
        backtrack(result, current+"(", open+1, close, max)
    }
    if close < open {
        backtrack(result, current+")", open, close+1, max)
    }
}

Complexity Analysis

The time complexity is O(4^n / sqrt(n)), as each valid sequence has at most n steps, and the number of valid sequences is the nth Catalan number. The space complexity is O(n) due to the recursion stack, not accounting for the space required to store the result.

Testing and Examples

Test cases include:

  • n = 1: Output should be ["()"]
  • n = 2: Output should be ["(())","()()"]
  • n = 3: Output should be ["((()))","(()())","(())()","()(())","()()()"]

Best Practices and Tips

Key takeaways include understanding the constraints of valid parentheses, leveraging backtracking to explore all possibilities, and optimizing the solution by pruning invalid paths early. Always validate your solution with edge cases like n = 1 and n = 8.

Read more