排列与组合问题

知识点之排列组合问题
排列组合问题常常使用回溯算法来解决问题，回溯算法的结构框架如下：

void backtracking(参数)
{
    if(终止条件)
    {
        存放结果；
        return;
    }
    for(选择：本层集合中元素(树中节点孩子的数量就是集合的大小))
    {
        处理节点；
        backtracking(路径，选择列表); //递归
        回溯，撤销处理结果;
    }
}

一 排列问题
对于长度为n的某数据进行排列总共有n!种排列方式(当然如果n个数据中存在一样的数据，那么排列的种类数目就会大大减少了)
使用回溯法，对于一个排列，我们可以将其分为第一个数据和后面的数据两个部分，依次将第一个数据和后面的每个数据进行交换(当然也可以使用一个标记数组)，确定了第一个数据后，接着去处理后面部分的数据，其方法和前面是一样的，这是一个递归的过程。具体代码如下：

vector<string> Permutation(string str)
{
    vector<string>ret;
    if (str == "")
        return ret;
    sort(str.begin(), str.end()); //对字符串进行升序排序，这样方便之后对重复的排列进行剪枝操作
    cout << str << endl;
    string tmp = "";
    vector<bool> vis(str.size(), false); //设置访问数组,能保证最后结果的字典序
    PermutationCore(ret, tmp, str, vis);
    return ret;
}

void PermutationCore(vector<string>&ret, string &tmp, string &str, vector<bool> &vis)
{
    if (str.size() == tmp.size())
    {

        ret.push_back(tmp); 
        return;
    }
    for (int i = 0; i < str.size(); ++i)
    {
        if (i > 0 && str[i] == str[i - 1] && !vis[i - 1])
            continue;
        if (!vis[i])
        {
            vis[i] = true; //加入处理
            tmp += str[i];
            PermutationCore(ret, tmp, str, vis);
            vis[i] = false; //回溯，撤销处理结果
            tmp.pop_back();
        }
    }
}

二 组合问题
对于长度为n的某数据进行组合总共有2^n-1种组合方式(当然如果n个数据中存在一样的数据，那么组合的种类数目就会大大减少了)
如果输入的数据长度为n，那么这n个字符能构成长度为1,2,…,n的组合，在求长度为m(1<=m<=n)的组合时，可以把n个字符分成第一个字符和后面的字符两个部分，如果组合里面包含第一个字符，则下一步就是在后面的字符中选取m-1个字符；如果组合里面不包含第一个字符，则下一步就是在后面的字符中选取m个字符。这样就形成了递归的函数调用关系f(m,n)=f(m-1,n-1)+f(m,n-1)。代码如下:

vector<vector<int> > Combination(vector<int>number)
{
    vector<vector<int> >ret;
    if (number.empty()) //数据为空就直接返回
        return ret;
    for (int i = 1; i<=number.size(); ++i) //选择长度为i的组合
    {
        vector<int>tmp; //tmp变量存放长度为i的组合结果
        CombinationCore(ret, number, 0, i, tmp); //每次都从第一个字符开始
    }
    return ret;
}
//下面是套用回溯算法的框架的代码
void CombinationCore(vector<vector<int> > &ret,vector<int> &number, int i, int m, vector<int>&tmp)
{
    if(m==0)
    {
        ret.push_back(tmp);
        return;
    }
    for(int j=i;j<number.size();++j)
    {
        tmp.push_back(number[j]);
        CombinationCore(ret,number,j+1,m-1,tmp);
        tmp.pop_back();
    }
}