2. 字符串的全部组合

题意：输出给定字符串的全部组合，如：输入abc, 输出a,b,c,ab,ac,bc,abc

算法实现

---

1. 递归实现

算法思想：假设从n个字符中选择m个字符，从头扫描字符串的第一个字符，针对第一个字符，有两种情况：

1. 在所选择的m个字符中，则在剩下的n-1个字符中，选择m-1个字符
2. 不在所选择的m个字符中，则在剩余n-1个字符中，选择m个字符

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <assert.h>

using namespace std;

void Combine(char * str, int num, vector<char> & result)
{
    if(num == 0)
    {
        for(int i = 0; i < result.size(); ++i)
            cout << result[i];
        cout << endl;
        return;
    }

    if(*str == '\0')
        return;

    result.push_back(*str);
    Combine(str+1, num-1, result);
    result.pop_back();

    Combine(str+1, num, result);
}

int main()
{
    //ifstream cin("in.txt");

    char str[100];
    while(cin >> str)
    {
        assert(str != NULL);
        int len = strlen(str);
        vector<char> ret;

        for(int i = 1; i <= len; ++i)
        {
            Combine(str, i, ret);   
        }
    }

    return 0;
}

2. 位运算实现

• 算法思想：n个字符的所有组合中，每个字符要么存在，要么不存在，共有32种，其中一种为空。如果使用0或1表示每位是否出现，则对于32中的任一种情况，只需计算1出现的位置，并输出响应位置的字符即可。如：10110，则输出str[1],str[2],str[4]（翻转后为01101）
• abc 输出结果为： a, b, ba, c, ca, cb, cba

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

string str;

void subset(int n, int num)
{
    cout << "(";
    for(int i = n-1; i >= 0; --i)  //逆序遍历，可以实现字典序输出
        if(num & (1 << i))
            cout << str[i];
    

    cout << ")" << endl;
}

int main()
{
    ifstream cin("in.txt"); 

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

        for(int i = 0; i < (1 << len); ++i)
        {
            subset(len, i);
        }

    }

    return 0;
}

3. 递归法，字典序输出

#include<stdio.h>

char num[]="abcde";
char rcd[26];

void full_combination(int l,int p)
{ 
    int i; 
    for(int i=0;i<l;i++) 
    { 
        printf("%c",rcd[i]); 
    } 
    printf("\n"); 

    for(i=p;i<5;i++)
    { 
        rcd[l]=num[i]; 
        full_combination(l+1,i+1); 
    }
}
int main()
{ 
    full_combination(0,0);

    return 0;
}