leetcode: Generate Parentheses

Problem Description:

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

Solution and Precautions:

We need to use backtracking (DFS) to enumerate all the possible legal parentheses sequence. Given n, the final string mush be of size 2*n, for each position in the final sequence, to generate the candidate “(” or “)”, we need to first check, whether (1) there are still “(” or “)” left (2) is it legal to put “)”? to put “)”, the condition is that there are unmatched “(” left, so basically we need to keep the information of the number of unmatched “(“, the number of remaining “(” and “)”. Then following standard backtracking algorithm, it should be solved.

Written on May 6, 2013