本文共 949 字，大约阅读时间需要 3 分钟。

问题：

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:

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

DFS，关键在于如何生成下一个树。

生成规则：  按顺序添加括号，左括号数量必定要大于等于右括号数量，否则的话不是匹配的括号对，剪枝。

如果左括号已经添加够n个，那么只需要继续添加右括号。

如果不是，那么添加左括号，或右括号，继续向下搜索。

如果左右括号数量都等于n,那么生成了一个可用的匹配。

参考：

代码：

class Solution {public:    vector
   
     generateParenthesis(int n) {        string str = "";        vector
    
      str_list;        DFS(str, 0, 0, n, str_list);        return str_list;    }    void DFS(string str, int left, int right, int n, vector
     
       &str_list)    {		if(left < right)			return;        if(left == n && right == n)		{            str_list.push_back(str);		}        else        {			if(left == n)				DFS(str+")", left, right+1, n, str_list);			else			{				DFS(str+")", left, right+1, n, str_list);				DFS(str+"(", left+1, right, n, str_list);			}        }    }};
     
    
   

转载地址：http://pktsi.baihongyu.com/