括号生成
一、题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1 输出：[“()”]
提示：
1 <= n <= 8
二、思路
这道题 自己思考了很久，除了暴力根本没有思路，哭了 。。
然后看了官方题解，写的也不是明白。还是大佬们发布的题解通俗易懂。
n对括号 肯定是n-1对括号加一对括号来的，而每个有效的括号组合肯定都是
‘(’ 开头，‘肯定也有一个’)'与它对应。那么这n-1对括号 可能在这对括号里面 或者 这对括号的外面.
( p ) q
p+q =n-1
p：0 ~ n-1
q：n-1 ~ 0
q在左边还是右边根本不影响的 。
所以 用四层for循环：
第一层 i ：第 i 对括号 ( 1~n）
第二层 j ：讨论 p 的 可能数(0~i-1) <p+q=i-1>
第三层 k：p第j种可能的第p种组合 j对括号的所有可能组合数的第p种
第四层m ：q第i-1-j种的第m种组合 i-1-j对括号的所有可能组合数的第
m种
三、代码
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<vector<string>> dp(n+1);
dp[0].push_back("");
dp[1].push_back("()");
for(int i=2;i<=n;i++){
for(int j=0;j<=i-1;j++){
for(int k=0;k<dp[j].size();k++){
for(int m=0;m<dp[i-1-j].size();m++){
dp[i].push_back("("+dp[j][k]+")"+dp[i-1-j][m]);
}
}
}
}
return dp[n];
}
};
看题解又学习了一下 C++11新特性(增强for循环) <java是这么叫 C++也是？>
auto:自动推导数据类型
for(auto p:dp[j]){
for(auto q:dp[i-1-j]){
dp[i].push_back("("+p+")"+q);
}
}
