问题描述

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:

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

想法与实现

涉及到全排列之类的事情,第一个想到的是递归。这个应该是最基础的做法。在这个问题里约束大致有两个,一个是括号对的个数,这个由输入给出,另外一个就是括号的匹配问题,一定要先有左括号再有右括号。这个问题就很容易用递归的思想去做,对于字符串s而言,每次可以选择增加一个左括号,或者在可以匹配到左括号的情况下增加一个右括号。所以是一个类似深度优先搜索的情况。最后得到的就是所有的全排列。

class Solution 
{
private:
	vector<string> res;
	int n; 
	void generateStr(int left, int right, string s, int rest)
	{
    	if (left == n && right == n)
    	{
	        res.push_back(s);
	        return; 
	    }
	    if (left != n) 
	        generateStr(left + 1, right, s + "(", rest + 1);
	    if (right != n && rest - 1 >= 0)
	        generateStr(left, right + 1, s + ")", rest - 1);
	    return;
	}

public:
	vector<string> generateParenthesis(int n) 
	{
	    this->n = n;
	    dfs(1, 0, "(", 1);
	    return res;
	}
};

评论