递归：codevs 1251 括号

codevs 1251 括号

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

计算乘法时，我们可以添加括号，来改变相乘的顺序，比如计算X1, X2, X3, X4, …, XN的积，可以

(X1(X2(X3(X4(...(XN-1*XN)...)))))

:::

(((...(((X1*X2)X3)X4)...)XN-1)XN)

你的任务是编程求出所有这样的添括号的方案。

输入描述 Input Description

输入文件第一行是一个数n（1<=n<=10），表示有n个变量，之后N行每行一个变量的名字。

输出描述 Output Description

输出所有的添加括号的方案。注意：单个字符不要加括号，两个字符相乘中间要有乘号。

样例输入 Sample Input

North

South

East

West

样例输出 Sample Output

(North(South(East*West)))

(North((South*East)West))

((North*South)(East*West))

((North(South*East))West)

(((North*South)East)West)

 1 /*不要尝试从样例数据的输出中寻找什么规律，事实上就是把这些字符串的前几个组合后几个组合（因为每个组合会有多种情况，所以返回的是字符串数组），再把两个的合并，那么就枚举前后组合的长度，边界，一个字符串，直接返回，两个字符串，中间加乘号，两边加括号返回*/
 2 #include<iostream>
 3 using namespace std;
 4 #include<cstdio>
 5 #include<vector>
 6 vector<string> dfs(string *ss,int begin,int end)
 7 {
 8     vector<string> ret;
 9     if(begin>end) return ret;
10     if(begin==end)
11     {
12         ret.push_back(ss[begin]);
13         return ret;
14     }
15     if(begin+1==end)
16     {
17         string s='('+ss[begin]+'*'+ss[end]+')';
18         ret.push_back(s);
19         return ret;
20     }
21     int size1,size2;
22     for(int i=begin;i<end;++i)
23     {
24         vector<string> s1=dfs(ss,begin,i);
25         vector<string> s2=dfs(ss,i+1,end);
26         size1=s1.size();size2=s2.size();
27         for(int j=0;j<size1;++j)
28           for(int k=0;k<size2;++k)
29           {
30               string s='('+s1[j]+s2[k]+')';/*注意这个中间没有乘号，因为题目中的括号与括号之间没有乘号的*/
31               ret.push_back(s);
32           }
33     }
34     return ret;
35 }
36 int main()
37 {
38     string ss[15];
39     int n;
40     scanf("%d",&n);
41     for(int i=1;i<=n;++i)
42       cin>>ss[i];
43     vector<string>ans=dfs(ss,1,n);
44     int size=ans.size();
45     for(int i=0;i<size;++i)
46       cout<<ans[i]<<endl;
47     return 0;
48 }