22. Generate Parentheses

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Problem Summary

Given n representing the number of pairs of parentheses to generate, write a function that can generate all possible and valid combinations of parentheses.

Solution Approach

• At first glance, this problem seems to require determining whether the parentheses match. If we really do the check, the time complexity would reach O(n * 2^n). Although it can still be AC, the time complexity is extremely high.
• This problem actually does not require determining whether the parentheses match. Because during the DFS backtracking process, ( and ) will be matched in pairs.

Code

package leetcode

func generateParenthesis(n int) []string {
	if n == 0 {
		return []string{}
	}
	res := []string{}
	findGenerateParenthesis(n, n, "", &res)
	return res
}

func findGenerateParenthesis(lindex, rindex int, str string, res *[]string) {
	if lindex == 0 && rindex == 0 {
		*res = append(*res, str)
		return
	}
	if lindex > 0 {
		findGenerateParenthesis(lindex-1, rindex, str+"(", res)
	}
	if rindex > 0 && lindex < rindex {
		findGenerateParenthesis(lindex, rindex-1, str+")", res)
	}
}