生成括号的唯一解决方案修复

Question

我尝试解决这个leetcode 22问题：给定数字n，生成括号。我知道还有其他方法可以解决这个问题；我只想知道为什么我的算法在数学上不起作用。 我试图通过将左开括号放置在每个有效位置，并通过将其与右括号交换，直到字符串((()))变为()()()来解决它。它对于小于等于3的数字有效，但对于大于3的数字无效。

vector<string> generateParenthesis(int n) {

    vector<string> fin;
    string baseString = "";

    for(int i = 0; i < n; i++) {
        baseString = "(" + baseString + ")";
    }
    fin.push_back(baseString);

    for(int l = n - 1; l > 0; l--) {
        int r = n;
        while (r < baseString.size() - 1) {
            // cout << "something";
            string cst = baseString;
            char temp = cst[r];
            cst[r] = cst[l];
            cst[l] = temp;
            r++;
            fin.push_back(cst);
        }
    }

    return fin;
}

有人能解释一下为什么它不能生成所有的组合，以及是否可以扩展它来实现这一点吗？

- 3shcodes

---

请考虑在此处发布：https://codegolf.stackexchange.com/ - ryanwebjackson

Answer 1

由于在内部循环的每次迭代中，cst字符串与baseString只有一个交换不同，而且在第一次循环构建后，baseString永远不会改变，因此算法无法正确处理更大的𝑛。

例如，对于𝑛=4，baseString将设置为(((())))。该算法将无法生成()()()()，因为从baseString开始至少需要两次交换。

另一种理解无法运作的方式是，创建的字符串数量为1 + (𝑛─1)²，而预期的字符串数量是𝐶_𝑛，即卡特兰数。

- trincot

---

你说得很对，发了一会儿帖子后我也发现了这点。想过如何检测是否需要多次交换，但这只会让算法变得更加复杂，哈哈。 - 3shcodes

Answer 2

有一种通用模式可以按字典顺序生成各种不同类型的序列：

给定“当前项”，您始终可以使用以下2个步骤创建下一个项：

1. 增加最右边的字符，该字符可以大于当前项中相应的字符。这是有效的，因为下一个项必须更大，并且在此情况下必须与当前项共享尽可能长的公共前缀。如果没有这样的字符，则已经生成了所有项。然后

2. 将其余字符设置为最低可能的值，否则您将跳过某些项而不是获取下一个项。

因此，让我们将其应用于从((()))到()()()的所有平衡括号序列：

1. 找到最右边的(，它可以更改为)。那是具有比关闭符号多的先前打开符号的最后一个打开符号。从((()))开始，例如，我们得到(()...。
2. 然后在其后添加所需数量的打开和关闭符号，首先是打开符号。这给我们(()())

让我们再做一次：（）（） -> （（）...... -> （（）（）

（（）（） -> （）...... -> （）（（）

（）（（） -> （）()...... -> （）（）（）

（）（）（） -> 完成

在C++中看起来像这样：

#include <iostream>
#include <string>

int main() {
    const int N = 6;
    std::string str;
    int opens = 0, closes = 0;
    do {
        for (;opens < N; ++opens) {
            str += '(';
        }
        for (;closes < N; ++closes) {
            str += ')';
        }
        std::cout << str << std::endl;
        
        // find the open to swap
        while(str.size() > 0) {
            char c = str.back();
            str.pop_back();
            if (c==')') {
                --closes;
            } else {
                --opens;
                if (opens > closes) {
                    str += ')';
                    ++closes;
                    break;
                }
            }
        }
    } while (!str.empty());
    return 0;
}

在ideone上试一试

- Matt Timmermans