LeetCode 22. 括号生成

Scroll Down

题目

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

 

示例:

输入:n = 3
输出:[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

链接:https://leetcode-cn.com/problems/generate-parentheses

解答

class Solution {
public:
	vector<string> ans;
	string tmpString = "(";
	void dfs(int left, int right) {
		if (left == 0) {
			string t=tmpString;
			for (int i = 0; i < right; i++) t.push_back(')');
			ans.push_back(t);
			return;
		}
		tmpString.push_back('(');
		dfs(left - 1, right);
		tmpString.pop_back();
		if (right > left) {
			tmpString.push_back(')');
			dfs(left, right - 1);
			tmpString.pop_back();
		}
	}
	vector<string> generateParenthesis(int n) {
		dfs(n-1, n);
		return ans;
	}
};