括号
- 难度：Medium
- 题目链接：https://leetcode-cn.com/problems/bracket-lcci/
题目描述
括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
解法：
逐个字符构造出括号组合，每一步都可能有两种选择，加入一个 ( 或者 )，条件是有剩余的括号可以用，且在选择加入 ) 时，需要保证已加入的左括号数大于右括号数。
基于以上考虑，使用 dfs 每次增加一个可行的括号。
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string s;
dfs(n, n, s, result);
return result;
}
void dfs(int left, int right, string& s, vector<string>& result){
if(left == 0 && right == 0){
result.push_back(s);
}else{
if(left > 0){
s.push_back('(');
dfs(left-1, right, s, result);
s.pop_back();
}
if(right > 0 && right > left){
s.push_back(')');
dfs(left, right-1, s, result);
s.pop_back();
}
}
}
};