Generate Parentheses

Medium

The problem

Given a number n, return every different string that has n pairs of round brackets and is correctly matched (every ( is closed by a later ) and nothing is closed before it is opened). The strings can be in any order.

Example 1
Input: n = 1
Output: ["()"]
The only way to match one pair.
Example 2
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
These are all 5 correctly matched strings with 3 pairs. For example "())(()" is not allowed because a ) comes before its (.

Limits

1 ≤ n ≤ 8

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You may add "(" while you have some left, and ")" only if it would not close more than you opened.

The idea

Backtrack building the string: add "(" if open < n, add ")" if close < open. When the length is 2n record it.

Target: O(4^n / √n) — the n-th Catalan number of results

Go function shape

func generateParenthesis(n int) []string

Reference solution

Tested with go test. Try it yourself first, then compare.

// GeneratePar: build the string one character at a time.
// Rule 1: you may add "(" while some are left. Rule 2: you may add ")" only if it closes an open one.
func GeneratePar(n int) []string {
	var out []string
	var build func(cur []byte, open, close int)
	build = func(cur []byte, open, close int) {
		if len(cur) == 2*n {
			out = append(out, string(cur))
			return
		}
		if open < n {
			build(append(cur, '('), open+1, close)
		}
		if close < open {
			build(append(cur, ')'), open, close+1)
		}
	}
	build(nil, 0, 0)
	return out
}

Read the lesson: Stack Basics