1. 输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

2. 实现一个算法打印出n对括号的有效组合。

1、思路：

　　假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。

1 #include 
     
       2 #include 
      
        3  4 using namespace std; 5  6 template 
       
         7 void PrintVector(vector
        
         & vec) 8 { 9     for (vector
         
          ::iterator iter = vec.begin(); iter != vec.end(); iter++)10         cout << *iter;11     cout << endl;12 }13 14 void StrComb(const char* str, vector
          
           & result, int num)15 {16 if (num == 0)17 PrintVector(result);18 else19 {20 if (*str == '\0') return;21 result.push_back(*str);22 StrComb(str + 1, result, num - 1);23 result.pop_back();24 StrComb(str + 1, result, num);25 }26 }27 28 int main()29 {30 char* str = "abc";31 vector
           
             result;32 int len = strlen(str);33 for (int i = 1; i <= len; i++)34 StrComb(str, result, i);35 }
           
          
         
        
       
      
     

 

2、思路：

　　 从左边起，取到任意的某个位置得到的串，左括号数量一定是大于或等于右括号的数量，只有在这种情况下，这组输出才是有效的。我们分别记左，右括号的数量为left和right，如下分析可看出，(()())是个有效的括号组合。只要还有左括号，我们就加入输出串，然后递归调用。当退出递归时，如果剩余的右括号数量比剩余的左括号数量多，我们就将右括号加入输出串。直到最后剩余的左括号和右括号都为0时，即可打印一个输出串。

1 void PareComb(int left, int right, vector
     
      & result) 2 { 3     //if (left < 0 || right < left) return; 4     if (left == 0 && right == 0) 5         PrintVector(result); 6     else 7     { 8         if (left > 0) 9         {10             result.push_back('(');11             PrintPare(left - 1, right, result);12             result.pop_back();13         }14         if (right > left)15         {16             result.push_back(')');17             PrintPare(left, right - 1, result);18             result.pop_back();19         }20     }21 }22 23 int main()24 {25     int num = 3;26     vector
      
        result;27     PrintPare(num, num, result);28 }