平衡的表达式，例如给定位置在C ++中有开括号？
在给定整数m和位置'position[]'（1<=length（position[]）<=2m）的数组的情况下，找到可以由长度2m构成的适当括号表达式的方式数目，使得给定的位置有开括号。
注意：position[]数组以（基于1的索引）[0，1，1，0]的形式提供。此处的1表示应将开括号设置在的位置。在值为0的位置，可以设置打开或关闭括号。
例子
Input: n = 2, position[] = [1, 0, 1, 0] Output: 1 The only possibility is given below: [ ] [ ] In this case, recursive and recursion implementing memorization approach will be explained.
算法
我们必须在给定数组adj1(say)中用方括号将所有位置标记为1。
我们以这种方式运行递归循环-
如果括号总数（括号从括号中减去）小于零，则返回0。
如果索引达到m且方括号总数等于0，则表示有解并返回1，否则返回0。
如果索引值有1预分配值，则必须递归地返回带有index+1的函数，并增加总括号。
否则，我们必须递归地返回该函数，方法是在该位置或索引处插入方括号，然后将总方括号增加1+在该索引处插入封闭方括号，然后将总方括号减少1，然后移至下一个索引，直到m。
以下是上述算法情况下的递归解决方案-
示例
// C++ application of above method implementing Recursion
#include <bits/stdc++.h>
using namespace std;
//查找或查找适当括号表达式的功能
int find(int index1, int openbrk1, int m, int adj1[]){
//如果开括号小于0-
if (openbrk1 < 0)
return 0;
//如果索引到达表达式的末尾
if (index1 == m) {
//如果括号是平衡的
if (openbrk1 == 0)
return 1;
else
return 0;
}
//如果当前索引已分配了方括号
if (adj1[index1] == 1) {
//我们必须继续提高
//开括号的长度
return find(index1 + 1, openbrk1 + 1, m, adj1);
}
else {
//我们还必须插入open-
//作为该索引的方括号
return find(index1 + 1, openbrk1 + 1, m, adj1)
+ find(index1 + 1, openbrk1 - 1, m, adj1);
}
}
//驱动程式码
int main(){
int m = 2;
//打开括号
int adj1[4] = { 1, 0, 0, 0 };
//调用find函数计算答案
cout << find(0, 0, 2 * m, adj1) << endl;
return 0;
}输出结果
2
记忆方式-通过实施记忆可以改善或优化上述算法的时间复杂度。
唯一要执行的是实现一个数组，以存储先前迭代的结果，因此，如果已经计算出该值，则不需要多次递归调用同一函数。
以下是必需的实现
// C++ application of above method implementing memorization
#include <bits/stdc++.h>
using namespace std;
#define M 1000
//查找或查找适当括号表达式的功能
int find(int index1, int openbrk1, int m,
int dp1[M][M], int adj1[]){
//如果开括号小于0-
if (openbrk1 < 0)
return 0;
//如果索引达到或到达表达式的末尾
if (index1 == m) {
//如果括号是平衡的
if (openbrk1 == 0)
return 1;
else
return 0;
}
//如果已经存储在dp1中
if (dp1[index1][openbrk1] != -1)
return dp1[index1][openbrk1];
//如果当前索引已分配了方括号
if (adj1[index1] == 1) {
//我们必须继续提高开括号的长度
dp1[index1][openbrk1] = find(index1 + 1,
openbrk1 + 1, m, dp1, adj1);
}
else {
//我们必须向前插入openas-
// well作为该索引的方括号
dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find(index1 + 1, openbrk1 - 1, m, dp1, adj1);
}
//我们必须返回答案
return dp1[index1][openbrk1];
}
//驱动程式码
int main(){
//dp1数组以预先计算答案
int dp1[M][M];
int m = 2;
memset(dp1, -1, sizeof(dp1));
//打开括号
int adj1[4] = { 1, 0, 0, 0 };
//我们必须调用find函数来计算答案
cout<< find(0, 0, 2 * m, dp1, adj1) << endl;
return 0;
}输出结果
2
时间复杂度：O(N2)