数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
class Solution {
List<String> ans = new ArrayList();
int num;
public List<String> generateParenthesis(int n) {
num=n;
String temp="";
dfs(0,0,temp);
return ans;
}
public void dfs(int lc,int rc,String temp){
if(lc>=num && rc>=num ){
ans.add(temp);
return;
}
if(lc<num) dfs(lc+1,rc,temp+"(");
if(rc<lc) dfs(lc,rc+1,temp+")");
}
}
在这之前尝试了类似于动态规划的解法,失败了
这是错的,很明显这样的DP没考虑到重构性.如n=4可以用两个n=2排列组合.
class Solution {
public List<String> generateParenthesis(int n) {
List<String> model = new ArrayList();
model.add("()");
for(int i=2;i<=n;i++){
List<String> temp = new ArrayList();
for(String s : model){
//并列添加
String mds1 = "()"+ s;
String mds2 = s + "()";
if(mds1.equals(mds2)){
temp.add(mds1);
}else {
temp.add(mds1);
temp.add(mds2);
}
//包含添加
temp.add("("+s+")");
}
model=temp;
}
Collections.sort(model);
return model;
}
}
参考了别人的解法
思路：动态规划
定义状态：
dp[i] 是一个数组，表示由 i 对括号生成的所有组合。
状态转移：
对于 0 <= j <= i-1, k = i - 1 - j，将 dp[j] 中所有的组合与 dp[k] 中所有的组合分别取出来，一一合并。
合并的时候不能将 dp[j] 中每一种组合与 dp[k] 中每一种组合直接合并，因为那样有重复的情况，不利于排除。
例如：
当 j = 1, k = 2 时：
dp[j] = ['()'];
dp[k] = ['()()', '(())'];
如果直接组合，得到的结果为：[ '( ) ( ) ( ) ', ' ( ) ( ( ) ) ' ]。
当 j = 2, k = 1 时：
dp[j] = ['()()', '(())'];
dp[k] = ['()']
如果直接组合，得到的结果为：[ ' ( ) ( ) ( ) ', ' ( ( ) ) ( ) ' ]。
此时会出现重复的情况：'()()()'。
而应该用一对括号将 dp[j] 中每一种组合括起来，并把 dp[k] 中每一种组合应该放到括号右边，这样就能保证合并之后每一种状态都是唯一的。
例如：
当 j = 1, k = 2 时：
dp[j] = ['()'];
dp[k] = ['()()', '(())'];
如果将 dp[j] 括起来再组合，得到的结果为：[ ' ( ( ) ) ( ) ( ) ', ' ( ( ) ) ( ( ) ) ' ]。
当 j = 2, k = 1 时：
dp[j] = ['()()', '(())'];
dp[k] = ['()'];
如果将 dp[j] 括起来再组合，得到的结果为：[ ' ( ( ) ( ) ) ( ) ', ' ( ( ( ) ) ) ( ) ' ]。
此时就没有重复的情况出现了。
初始状态：
dp[i] = [];
dp[0] = [''];
dp[1] = ['()'];
代码
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
const dp = new Array(n + 1).fill(false).map(() => []);
dp[0] = [''];
dp[1] = ['()'];
for(let i = 2; i <= n; i++) {
for(let j = 0; j < i; j++) {
let k = i - 1 - j;
// dp[i] += dp[j] * dp[k];
for(let jj = 0; jj < dp[j].length; jj++) {
for(let kk = 0; kk < dp[k].length; kk++) {
dp[i].push(`(${dp[j][jj]})${dp[k][kk]}`);
}
}
}
}
// console.log(dp[n]);
return dp[n];
};
// const n = 4
// generateParenthesis(n);
作者：20182726
链接：https://leetcode-cn.com/problems/generate-parentheses/solution/by-20182726-ci8b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。