使用递归的合法括号对序列 - Python

Question

我有一些问题需要在 Python 中使用递归来解决。我只是递归不好，不知道如何开始所以请指导我。

We will say that a string contains 'n' legal pairs of parentheses if the string contains only the chars '(',')' and if this sequence of parentheses can be written so in a manner of mathematical formula (That is, every opening of parentheses is closed and parentheses are not closed before they are opened). More precise way to describe it is at the beginning of the string the number of '(' is greater or equal to ')' - and the number of any kind of char in the whole string is equal. Implement a function that recieves a positive integer n and returns a list which contains every legal string of n-combination of the parentheses.

我已经尝试至少开始，想想一个基本案例，但我的基本案例到底是什么？

当我得到最小 n，即 1，然后我想我必须 return 一个列表 ['(', ')'] 时，我试图考虑一个基本情况。但是要做到这一点我也有困难...

def parentheses(n):
    if n == 1:
        return combine_parent(n)

def combine_parent(n):
    parenth_lst = []
    for i in range(n):
        parenth_lst +=

请向我解释递归解决问题的方法。

谢谢！

Answer 1

也许查看一个简单的问题案例会有所帮助：

n = 2
(())
()()

所以我们从 n=2 开始，我们生成 ( n 次的序列，然后是 ) n 次的序列，然后我们 return 一个列表.然后我们用 n-1 递归地做。当我们达到 n=1 时，看起来我们达到了基本情况，即我们需要 return 一个带有 () 的字符串 n 次（不是 n=1，而是 n=2）。

n = 3
((()))
(())()
()()()

n=3 的模式相同。

以上例子有助于理解如何递归解决问题。

def legal_parentheses(n, nn=None):
    if nn == 1:
        return ["()" * n]
    else:
        if not nn:
            nn = n

        # This will produce n ( followed by n ) ( i.e n=2 -> (()) )
        string = "".join(["(" * nn, ")" * nn])

        if nn < n:
            # Then here we want to produce () n-nn times.
            string += "()" * (n-nn)

        return [string] + legal_parentheses(n, nn-1)

print(legal_parentheses(3))
print(legal_parentheses(4))
print(legal_parentheses(5))

对于 n = 3:

['((()))', '(())()', '()()()']

对于 n = 4:

['(((())))', '((()))()', '(())()()', '()()()()']

对于 n = 5:

['((((()))))', '(((())))()', '((()))()()', '(())()()()', '()()()()()']

这是解决问题的一种方法。

在我看来，考虑递归解决问题的方法是首先选择你的问题中最简单的例子，n=2然后写下你对结果的期望。在这种情况下，您期望得到以下输出：

"(())", "()()"

现在，您正试图找到一种策略来分解问题，以便您可以生成每个字符串。我首先考虑基本情况。我说简单的情况是当结果是 ()() 时，我知道那个结果的一个元素只是 () n 次。如果 n=2，我应该期待 ()()，而当 n=3 我应该期待 ()()() 并且序列中应该只有一个这样的元素（所以它应该只完成一次）因此它成为基本情况。问题是我们如何计算结果的 (()) 部分。模式显示我们只需将 n ( 后跟 n ) -> (()) for n=2。这看起来是个好策略。现在你需要开始思考一个稍微难一点的问题，看看我们的策略是否仍然有效。

所以让我们想想n=3。我们期望结果如何？

'((()))', '(())()', '()()()'

好的，我们看到基本情况应该仍然产生 ()()() 部分，一切都很好，并且还应该产生 ((())) 部分。 (())() 部分呢？看起来我们需要一种稍微不同的方法。在这种情况下，我们需要以某种方式生成 n ( 后跟 n ) 然后生成 n-1 ( 后跟 n-1 ) 然后n-2 ( 之后是 n-2 ) 等等，直到我们到达基本情况 n=1 我们将要生成 () 部分 n 次。但是，如果我们每次都用 n-1 调用该函数，那么当我们到达基本情况时，我们不知道原始 n 值是什么，因此我们无法生成 () 部分因为我们不知道我们想要多少（如果原来的 n 是 3 那么我们需要 ()()() 但是如果我们通过使用 n-1 调用函数来更改 n 那么通过当我们达到基本情况时，我们将不知道原始 n 值）。因此，正因为如此，在我的解决方案中，我引入了第二个名为 nn 的变量，该变量每次都会减少，但我们仍然保持 n 不变，因此我们知道原始值是多少。

使用递归的合法括号对序列 - Python

Sequence of legal pairs of parentheses using recursion - Python

python-3.x

recursion

recursive-backtracking