生成括号问题的闭包数法

Question

Leetcode上的Generate Parenthesis标准题如下

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

他们在解决方案选项卡中解释了 Closure Number Method，我觉得这很难理解。

我对代码进行了干练运行，甚至得到了正确答案，但似乎无法理解它为什么有效？这种方法背后的直觉是什么？

如有任何帮助，我们将不胜感激！

Answer 1

该算法的基本思想是动态规划。因此，您尝试 将您的问题分解为易于解决的较小问题 。在此示例中，您将 sub-problems 设置得非常小，以至于解决方案要么是空字符串（如果大小为 0），要么解决方案是“()”（对于大小 1）。

您开始使用这样的知识：如果您想要给定长度的括号，那么 第一个字符需要是“(”，并且在字符串后面的某个位置需要这个字符： ")"。否则输出无效。

现在您不知道右括号的位置，所以您只需尝试每个位置（第一个 for 循环）。

你知道的第二件事是，在左括号和右括号之间以及右括号之后必须有一些东西，你真的不知道它看起来如何（因为有很多可能性），但是它 必须再次成为有效的括号对 。

现在这个问题正是您已经解决的问题。因此，您只需放入有效括号的所有可能性（使用较小的输入大小）。因为这正是您的算法已经执行的操作，您可以使用递归函数调用来执行此操作。

如此总结：你知道问题的一部分，剩下的问题就是同一个问题，只是规模小了点。所以你解决了你知道的问题的一小部分，并递归地调用相同的方法来解决问题的其余部分。之后你只需将它们放在一起并得到你的解决方案。

动态编程通常不是那么容易理解但非常强大。因此，如果您不直接理解它，请不要担心。解决这样的难题是学习动态规划的最好方法。

Answer 2

一个序列的闭包数，其大小为序列的最小前缀，它本身就是一个有效序列。如果一个序列的闭包号为 k，那么您知道在索引 0 中有 '('，在索引 k 中有 ')' 该方法通过检查此类前缀的所有可能大小来解决问题，对于每个前缀，它将序列打断为前缀（删除 0 和 k 元素）和序列的所有其余部分，并递归地解决两个子问题。

生成括号问题的闭包数法

Closure Number Method for Generate Parenthesis Problem

algorithm

catalan