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我发现很难理解的。
我对代码进行了试运行，甚至得到了正确的答案，但似乎无法理解它为什么起作用？这种方法背后的直觉是什么？
任何帮助将不胜感激！
该算法的基本思想是动态规划。因此，您尝试将问题分解为易于解决的较小问题。在此示例中，您将子问题设置得非常小，以致解为空字符串（如果大小为 0）或解为“()”（对于大小 1）。
您开始使用以下知识：如果您想要给定长度的括号，那么第一个字符需要是“(”，并且在字符串的后面某个位置需要有这个字符：“)”。否则输出无效。
现在您不知道右括号的位置，因此您只需尝试每个位置（第一个 for 循环）。
你知道的第二件事是，在左括号和右括号之间以及在右括号之后，必须有一些东西，你并不真正知道它看起来如何（因为有很多可能性），但它必须是一个再次有效的括号对。
现在这个问题就是你已经解决的问题了。因此，您只需输入有效括号的所有可能性（使用较小的输入大小）。因为这正是您的算法已经执行的操作，所以您可以使用递归函数调用来执行此操作。
总结一下：你知道问题的一部分，而问题的其余部分只是同样的问题，只是规模较小。因此，您解决了已知问题的一小部分，并递归调用相同的方法来解决问题的其余部分。然后，您只需将所有内容放在一起即可得到解决方案。
动态编程通常不太容易理解，但功能却非常强大。因此，如果您不能直接理解它，请不要担心。解决此类难题是学习动态规划的最佳方法。