22

题目

方法一：暴力破解，遍历所有的结果，对所有结果进行判断。数据量大的话可能会超时。

var generateParenthesis = function(n) {
  let arr = [];
  function dp(n,idx,str){
    if(idx===n){
      if(juge(str)){
        arr.push(str);
      }
      return;
    }
    dp(n,idx+1,`${str}(`);
    dp(n,idx+1,`${str})`);
  }
  dp(n*2,0,'');
  return arr;
};
function juge(str){
  let stack = [];
  for(let i=0;i<str.length;i++){
    if(str[i]===')'){
      if(stack.pop()!=="(")return false;
    }else{
      stack.push(str[i]);
    }
  }
  if(stack.length!==0)return false;
  return true;
}

方法二：回溯，其实方法一也算是回溯，但是方法一回溯了所有情况，而且每次返回的结果还要用栈来判断是否合法，但是方法二的回溯只回溯有效值。

var generateParenthesis = function(n) {
  let arr = [];
  function dp(left,right,str){
    if(left===0&&right===0){
      arr.push(str);
      return;
    }
    if(left>0){
      dp(left-1,right,`${str}(`);
    }
    if(right>left){
      dp(left,right-1,`${str})`);
    }
  }
  dp(n,n,'');
  return arr;
};