Topic:

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations. The combination of valid brackets must meet the following requirements: The left bracket must be closed in the correct sequence.

Example 1:

Input: n = 3 output: [” ((())) “, “() () ()”, “() () ()”, “() () ()”, “() () ()”]

Example 2:

Output: [“()”]

Methods a

Analysis:
  • Must begin with an open parenthesis
  • The number of close parentheses is equal to the number of open parentheses
  • Each position is either an open parenthesis or a close parenthesis, n pairs of parentheses, 2N characters, totalTwo to the 2n is possible
  • Each position generates an open parenthesis or a close parenthesis, and you can use recursion

First check if the string is a reasonable combination, set the count variable, encounter the open parenthesis +1, encounter the close parenthesis -1. In the process, a negative count is not a reasonable combination, and a zero final result is a reasonable combination.

var valid = function (str) {
  let count = 0;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') {
      count++;
    } else {
      count--;
    }
    if (count < 0) {
      return false; }}return count === 0;
}
Copy the code

Find all possible strings again:

var all = function (cur, n, strArr) {
  if (cur.length === n) {
    if(valid(cur)) {
      strArr.push(cur);
    }
    return cur;
  }
  cur += '(';
  cur = all(cur, n, strArr);
  cur = cur.slice(0, cur.length - 1);
  cur += ') ';
  cur = all(cur, n, strArr);
  cur = cur.slice(0, cur.length - 1);
  return cur;
}
Copy the code
Complete code:
/ * * *@param {number} n
 * @return {string[]}* /
var generateParenthesis = function(n) {
  var valid = function (str) {
    let count = 0;
    for (let i = 0; i < str.length; i++) {
      if (str[i] === '(') {
        count++;
      } else {
        count--;
      }

      if (count < 0) {
        return false; }}return count === 0;
  }
  
  var allStr = function (cur, n, strArr) {
    if (cur.length === n) {
      if(valid(cur)) {
        strArr.push(cur);
      }
      return cur;
    }

    cur += '(';
    cur = allStr(cur, n, strArr);
    cur = cur.slice(0, cur.length - 1);
    cur += ') ';
    cur = allStr(cur, n, strArr);
    cur = cur.slice(0, cur.length - 1);
    return cur;
  }
  
  let arr = [];
  let str = ' ';
  allStr(str, n * 2, arr);
  return arr;
};
Copy the code

Method 2

Analysis:
  • If the number of open parentheses is less than n, you can put an open parentheses, if the number of open parentheses is less than n, you can put a close parentheses.
Complete code:
/ * * *@param {number} n
 * @return {string[]}* /
var generateParenthesis = function(n) {
  var backtrack = function (strArr, cur, left, right, n) {
    if (cur.length === 2 * n) {
      strArr.push(cur);
      return cur;
    }

    if (left < n) {
      cur += '(';
      cur = backtrack(strArr, cur, left + 1, right, n);
      cur = cur.slice(0, cur.length - 1);
    }

    if (right < left) {
      cur += ') ';
      cur = backtrack(strArr, cur, left, right + 1, n);
      cur = cur.slice(0, cur.length - 1);
    }
    return cur;
  }

  let arr = [];
  let str = ' ';
  backtrack(arr, str, 0.0, n);
  return arr;
};
Copy the code

Methods three

Analysis:
  • Repeatedly insert an existing string with () as the smallest unit
Complete code:
/ * * *@param {number} n
 * @return {string[]}* /
var generateParenthesis = function(n) {
  if (n === 1) {
    return [ '()' ];
  }

  let set = new Set(a);let str = ' ';
  for (item of generateParenthesis(n - 1)) {
    for (let i = 0; i < 2 * (n - 1); i++) {
      str = item.substr(0, i) + '()' + item.substr(i, 2 * (n - 1));
      set.add(str)
    }
  }
  
  return [...set];
};
Copy the code