22. Generate Parentheses 生成括号

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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Difficulty: Medium

这道题让我们列举出所有的括号字符串,前面还有一题20. Valid Parentheses 验证括号也是关于括号的.这里让列举出所有可能,可以优先考虑递归和DFS.定义left,right分别表示剩余左括号的数量和剩余的右括号的数量.如果在某次的递归中,left>right说明在已经生成的字符串中右括号的数量大于左括号的数量,是不合理的.当left,right都为0的时候,说明已经生成一个可用的括号串.其实这里有DFS的思想.为什么呢.看看下面是怎样递归的顺序,以题目给的例子n=3.

(
((
(((
((()
((())
((()))
(()())
  ~
()()()

DFS(深度优先),这里可以想象成左括号优先

解法1

就是上面分析的解法

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        generateParenthesisDFS(n,n,"",res);
        return res;
    }
    void generateParenthesisDFS(int left,int right,string out,vector<string>& res)
    {
        if (left>right) return;
        if (left==0 && right==0) res.push_back(out);
        else{
            if (left>0) generateParenthesisDFS(left-1,right,out+'(',res);
            if (right>0) generateParenthesisDFS(left,right-1,out+')',res); 
        }
    }
};

解法2

可以借助图的结构思考.关于图简单了解可以看下图的基本算法(BFS和DFS).在这里可以把当前节点用(x,y),x代表当前位置左括号数,y代表当前位置右括号数, 有(x>=y).图的边可以看做为从(x,y)到(x+1,y)和(x,y+1).当x==y时,没有(x,y+1)这条边. 所以这道题可以看成为求从(0,0)出发到(n,n)的全部路径.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        generateParenthesisDFS(n,0,0,"",res);
        return res;
    }
    void generateParenthesisDFS(int n,int x,int y,string out,vector<string>& res)
    {
        if (y==n) res.push_back(out);
        if (x<n) generateParenthesisDFS(n,x+1,y,out+'(',res);
        if (x>y) generateParenthesisDFS(n,x,y+1,out+')',res);
    }
};
 
comments powered by Disqus