René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"22.括号生成","articleBody":"[原题地址](https://leetcode-cn.com/problems/generate-parentheses/)\r\n\r\n给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。\r\n例如，给出 n = 3，生成结果为：\r\n```\r\n[\r\n  \"((()))\",\r\n  \"(()())\",\r\n  \"(())()\",\r\n  \"()(())\",\r\n  \"()()()\"\r\n]\r\n```\r\n\r\n### 解法\r\n#### 动态规划\r\nn对合法括号可以通过以下形式构造\r\nf(n) = '(' + f(p) + ')' + f(q)\r\n\r\n``` js\r\n/**\r\n * @param {number} n\r\n * @return {string[]}\r\n */\r\nvar generateParenthesis = function(n) {\r\n  let map = new Array(n + 1).map(item =\u003e [])\r\n  map[0] = [''];\r\n  map[1] = ['()'];\r\n  for (let i = 2; i \u003c= n; i++) {\r\n    let cur = []\r\n    for (let j = 0; j \u003c i; j++) {\r\n      let left = map[j]\r\n      let right = map[i - 1 - j \u003e 0 ? i - 1 - j : 0]\r\n      for (let k = 0; k \u003c left.length; k++) {\r\n        for (let m = 0; m \u003c right.length; m++) {\r\n          cur.push(`(${left[k]})${right[m]}`)\r\n        }\r\n      }\r\n    }\r\n    map[i] = cur;\r\n  }\r\n\r\n  return map[n]\r\n};\r\n```\r\n\r\n#### 深搜回溯\r\n\r\n要去构造一个合法括号序列，只需要保证\r\n1. left大于等于right\r\n2. 当left === right时，下一个括号必须是左括号\r\n其中left是左括号数量，right是右括号数量\r\n\r\n```js\r\n// @lc code=start\r\n/**\r\n * @param {number} n\r\n * @return {string[]}\r\n */\r\nvar generateParenthesis = function(n) {\r\n  let res = []\r\n  solve(0, 0, '');\r\n  return res;\r\n\r\n  function solve(left, right, cur) {\r\n    if (left === n \u0026\u0026 right === n) {\r\n      res.push(cur)\r\n      return\r\n    }\r\n\r\n    if (left \u003e= right) {\r\n      if (left \u003e right) {\r\n        left \u003c n \u0026\u0026 solve(left + 1, right, cur + '(')\r\n        right \u003c n \u0026\u0026 solve(left, right + 1, cur + ')')\r\n      } else {\r\n        left \u003c n \u0026\u0026 solve(left + 1, right, cur + '(')\r\n      }\r\n    }\r\n  }\r\n};\r\n```\r\n\r\n\r\n\r\n\r\n\r\n\r\n","author":{"url":"https://github.com/feikerwu","@type":"Person","name":"feikerwu"},"datePublished":"2020-02-26T07:44:50.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/2/algorithm-camp/issues/2"}