Problem overview
The function generateParentheses receives n, the number of pairs of parentheses, and returns every well-formed string made of exactly n pairs. A string is well-formed when every ( is closed by a later ) and no ) appears before its matching (.
For n = 3 the answer has five strings: ((())), (()()), (())(), ()(()) and ()()(). For n = 1 the only string is ().
Approach: build the string one character at a time
A string with n pairs has length 2n, and each position holds either ( or ). The naive plan generates all 2^(2n) strings and keeps the balanced ones. For n = 8 that is 65,536 strings to inspect, and the count doubles with every extra character.
Backtracking avoids most of that work by refusing to build prefixes that can't be completed. Two facts make a prefix hopeless:
- It contains more
)than(. No later character can fix that, because a closing parenthesis can only match an opening one that came before it. - Its surplus of
(over)is larger than the number of positions left. Even if every remaining character were), some opening parentheses would stay unmatched.
With both checks in place, every prefix that survives can still become a well-formed string, so the recursion never wanders into dead ends for long. A string that reaches length 2n and passed both checks is balanced: the first check says closed never exceeded open, and the second says open can't exceed closed when no positions are left, so the two counts are equal.
The recursion tracks the current string, the number of ( used (open) and the number of ) used (closed). At each position it tries ( first, then ).
Step by step
- Create the result slice.
solutionsstarts as an empty[]stringingenerateParentheses. - Start the recursion with an empty string, the target length
2*n, both counters at zero and the address ofsolutions. - Return the slice once the recursion has filled it.
- Declare the helper
generateParenthesis(one letter shorter than the main function's name) with the parameterscurrent,length,open,closedandsolutions *[]string. - First guard: return if
open < closed, a prefix that closed too much. - Second guard: return if
openexceedsclosedplus the remaining positionslength - len(current). - Record complete strings. When
len(current) == length, appendcurrentto the results and return. - Recurse twice: once with
current+"("andopen+1, once withcurrent+")"andclosed+1.
The solution in Go
func generateParentheses(n int) []string {
solutions := []string{}
generateParenthesis("", 2*n, 0, 0, &solutions)
return solutions
}
func generateParenthesis(current string, length, open, closed int, solutions *[]string) {
if open < closed {
return
}
if open > closed+(length-len(current)) {
return
}
if len(current) == length {
*solutions = append(*solutions, current)
return
}
generateParenthesis(current+"(", length, open+1, closed, solutions)
generateParenthesis(current+")", length, open, closed+1, solutions)
}
The Go details worth knowing:
- Why a pointer to a slice. A slice is a small header holding a pointer to its array, a length and a capacity. Passing it to a function copies the header. If the function calls
appendand the array has to grow, only the copy sees the new elements. Given a sliceawith length 0, a functionaddByValue(s []string)that runss = append(s, "x")leaveslen(a)at 0, while a function taking*[]stringand running*s = append(*s, "x")makeslen(a)1. That is why the helper takessolutions *[]string, passes&solutionsfrom the caller and writes through*solutions. - Strings are immutable values.
current+"("builds a new string and leavescurrentalone. The second recursive call therefore still sees the original prefix, and no undo step is needed, unlike backtracking on a shared board. - Shared parameter types.
length, open, closed intdeclares threeintparameters at once. - Order of the output. Trying
(before)produces the strings in dictionary order, with((()))first and()()()last, the same order as the example.
Complexity
The number of well-formed strings with n pairs is the Catalan number: 1, 2, 5, 14 and 42 for n from 1 to 5, and 1,430 for n = 8. It grows like 4^n divided by roughly n to the power 1.5, so the output alone sets the cost. Since every prefix the recursion accepts can be extended to a valid string, the number of calls is at most about 2n times the number of results, and each string concatenation costs up to O(n).
Time: proportional to the number of results times a polynomial in n, far below the 2^(2n) strings of the naive plan. Space: the recursion is at most 2n calls deep, with a string of up to 2n characters per call, which is O(n^2) beyond the output itself.
Edge cases and common mistakes
- Passing the slice by value. The code compiles and runs, but the caller gets an empty slice back.
- Skipping the second guard. The first guard alone lets
((((reach length 4 forn = 2, and the code would append it as an answer. The second guard rejects it as soon as the surplus of(exceeds the positions left. - Using
open <= closedin the first guard. A balanced prefix such as()has equal counts, and it must continue. - Checking the length before the guards. A full-length string would be appended without proof that it is balanced. The guards run first for that reason.
- Counting positions with the wrong value. The positions left are
length - len(current), wherelengthis2*n, notn. - Strings are bytes.
len(current)counts bytes, which is the same as characters here because both parentheses are ASCII.
Testing
generateParentheses(1)gives[()].generateParentheses(3)gives[((())) (()()) (())() ()(()) ()()()]when printed withfmt.Println.len(generateParentheses(8))is1430.