（*）剑指offer 面试题28：字符串的全排列

题目：
输入一个字符串，打印出该字符串中字符的所有排列。

解法：
递归的思路。以abc为例，固定首字母，剩余部分全排列即可。

void permutation(char* str, char* pBegin)  {
    if (str == 0 || pBegin == 0)  return;
    if (*pBegin == '\0') {
        cout << str << endl;
    } else {
        for (char *pCh = pBegin; *pCh != '\0'; ++pCh) {
            char  tmp  =  *pCh;
            *pCh  =  *pBegin;
            *PBegin  =  tmp;

            permutation(str, pBegin+1);
            
            tmp = *pCh;
            *pCh  =  *pBegin;
            *PBegin  =  tmp;
        }
    }
}

扩展题目：
求一个字符串所有的组合
解法：
给定一个长度为n的字符，所有组合即为取1个、2个、...、m个、...、n个字符的组合之和。
记从n个字符中取出m个字符的所有组合为g(n,m)，则g(n,m) = g(n-1,m-1) + g(n-1,m)：取第一个字符，则从剩下的n-1个字符中取m-1个字符；不取第一个字符，则从剩下的n-1个字符中取m个字符。

void combination(char *str) {
    int len = strlen(str);
    vector<char>  result;
    for (int i = 1; i <= len; ++i) {
        combination_recursive(str, i, result);
    }
}

void combination_recursive(char *str, int number, vector<char>& result) {
    if (result == 0)  return;
    if (number == 0)  {
        print(result);
        return;
    }

    result.push_back(*str);
    combination_recursive(str+1, number-1, result); 
    result.pop_back();

    combination(str+1, number, result);
}