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.

Tips and Divergent thinking:



(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on May 6, 2013