感觉像深搜……

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
string str;
int len;
int cnt;
void DFS(int start ,int end,int deep,string & result) {
    if(deep == len - 1) {
        cout << result << endl;
        cnt++;
        return ;
    }
    if(start > 0) {
        string temp = result;
        result.insert(0,str.substr(start-1,1));
        result.insert(0,"(");
        result.append(")");
        DFS(start - 1,end,deep+1,result);
        result = temp;
    }

    if(end < len - 1) {
        string temp = result;
        result.insert(result.length(),str.substr(end+1,1));
        result.insert(0,"(");
        result.append(")");
        DFS(start,end+1,deep+1,result);
        result = temp;
    }
}

int main() {
    cin >> str;
    len = str.length();

    for(int i = 0; i < len-1; i++){
            string t = str.substr(i,2);
            t.insert(0,"(");
            t.append(")");
            DFS(i,i+1,1,t);
    }
    cout << "cnt = " << cnt ;
    return 0;
}

全局变量默认是0

    就拿4个字符的集合来说明
 看看提示
((( 1 2 )3 )4))--------1234分别代表一个框
第一个框能放的元素方法有4种
第二个框能放的元素方法有3
第三个框能放的元素方法有2
第四个框能放的元素方法有1

字母排列总数=4！
还的考虑括号的排列。
这种计数问题非常适合递归。可惜 我现在不会

[ 本帖最后由 okayyyy 于 2010-8-22 22:02 编辑 ]

不是的，楼主的题目有规定下一个括号只能有两种选择，你看看题目吧，御坂提醒道

那就简单了，只要考虑第一对括号能出现的位置。
拿上面的问题来说就只有3中组合

所以总数=4！*3
现在是绝对没问题了

楼上的，你的粉丝很多啊，不管马腿，马屁一通乱拍。

[ 本帖最后由 okayyyy 于 2010-8-22 22:21 编辑 ]

something else

[ 本帖最后由 succubus 于 2010-8-26 23:42 编辑 ]

又算了算 每个字符序列 分别得考虑括号组合，  这个总数还真是大。
别说什么归纳法了，排列组合都记不清楚了

再算了算，每个序列的括号排列又有1 + 3 + 3 + 1
计算排列的总数，n!                 
再计算每个排列的括号排列2^(n-2)  
得n!* 2^(n-2)
                                             
我不信我的解题方法有问题。思路是一点问题都没

我倒想问问2^(n-2)的结果到底是怎么得来的
由2^(n-2)可知，n=3是：只有2种组合，呵呵 你去排排看。只有2种吗？
((a b) c) (a (b c))
别说浮躁   a b c a c b  b a c    b c a  c a b  c b a 那我问这这个没排的怎么办？你帮我用归纳法证明下

[ 本帖最后由 okayyyy 于 2010-8-23 01:54 编辑 ]

我忏悔阿门 保佑我

nothing


[ 本帖最后由 succubus 于 2010-8-26 23:41 编辑 ]