生成括号唯一解修复

Question

所以我试图解决这个 leetcode 22 问题 generate parantheses with a given number n。我知道还有其他方法可以解决这个问题我只是想知道为什么我的算法在数学上不起作用。 我试图通过将左开括号与右括号交换直到字符串 ((())) 到达 ()()() 来将左开括号放在每个有效位置。它最多适用于 3 个，但不能超过 3 个。

type here
    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<<"someshit";
                string cst=baseString;
                char temp=cst[r];
                cst[r]=cst[l];
                cst[l]=temp;
                r++;
                fin.push_back(cst);
            }
        }

        return fin;
    }

任何人都可以解释为什么它不能生成所有组合，以及是否可以扩展它来生成所有组合？

Answer 1

对于较大的 𝑛，该算法无法正常工作，因为在内部循环的每次迭代中，

cst

字符串仅与

baseString

不同，并且

baseString

在第一个循环中构建后永远不会改变。

例如，对于 𝑛=4，

baseString

将设置为

(((())))

。该算法将无法生成

()()()()

，因为从 baseString 开始时至少需要

two

交换。

另一种理解为什么它不起作用的方法是创建的字符串数是 1 + (𝑛─1)²，而预期的字符串数是𝐶_𝑛，即加泰罗尼亚数字.

Answer 2

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

给定“当前项目”，您始终可以通过以下两个步骤制作下一个项目：

1. 递增最右边可以大于当前项中对应字符的字符。这是可行的，因为下一个项目必须更大，并且鉴于此，必须与当前项目共享最长的可能前缀。如果没有这样的字符，那么你已经生成了所有项目。那么

2. 将剩余的字符设置为尽可能低的值，否则你会跳过一些项目而不是获取下一个。

所以让我们应用它来获得从

((()))

到

()()()

的所有平衡括号序列：

1. 找到最右边的可以变成

   (

   的

   )

   。这是最后一次开盘，之前的开盘次数多于收盘次数。例如，从

   ((()))

   开始，我们得到

   (()...

   。
2. 然后在其后添加所需的打开和关闭次数，首先打开。这给了我们

   (()())

让我们再做一次：

(()())

->

(())...

->

(())()

(())()

->

()...

->

()(())

()(())

->

()()...

->

()()()

()()()

-> 完成