130. 自动生成括号

[goldEli]

leetcode-22

写一个方法可以生成 n 对有效的括号：

Input: 
n = 3

Output:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {

}

[goldEli]

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  const res = []  
  function step(item) {
      if (item.length === n*2) {
        res.push([...item])
        return
      }
      for (let i = 0; i < 2; ++i) {
        item.push(i)
        step(item)
        item.pop()   
      }   
  }

  step([])

  return res
    .filter(item => item[0] === 0)
    .filter(item => checkValidiy(item))
    .map(item => item.map(i => PARENTHESIS_MAP[i]).join(""))
};

var PARENTHESIS_MAP = {
  0: "(",
  1: ")",
}

var checkValidiy = function(arr) {
  const stack = []
  for (let i = 0; i < arr.length; ++i) {
    if (arr[i] === 0) {
      stack.push(arr[i])
    } else if (arr[i] === 1) {
      if (stack.pop() + arr[i] !== 1) {
        return false
      }
    }
  }
  if (stack.length > 0) return false
  return true
}

[zlx362211854]

function generateParenthesis(n) {
  var result = new Array();
  if (n == 0) {
    result.push("");
  } else {
    for (let i = 0; i < n; ++i) {
      generateParenthesis(i).forEach(left => {
        generateParenthesis(n - 1 - i).forEach(right => {
          result.push("(" + left + ")" + right);
        })
      })
    }
  }
  return result;
}
generateParenthesis(3)

i是left中的括号对数，一个括号对包括一个'('和一个配套的')'，总括号对数是n，除去left中的括号对数，以及left前面的'('加上left和right之间的')'构成的一个括号对，right中的括号对数就是n-1-i