全排列

刷到剑指offer的一道全排列的题，如下：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

不难看出这就是高中数学的排列。N个字符的排序共有N！个。那么怎么用代码去打印出字符串的排列呢？

当然我们可以用for循环，对于每一位都用一次for循环。比如说从第一位开始，第一位有3个选择；当第一位是a的时候，第二位就会有两种选择，以此类推，但是这样的话，时间复杂度就是O(N^N)，太复杂了。

显然我们可以把这个字符串每次分成两个部分，第一部分是第一个位置，剩下的所有是另一个部分。第一步求出第一个位置所有可能的字符，然后把后面所有的字符和第一个字符交换。第二步就是固定第一个位置的字母，对剩下的部分进行相同的操作，直到这个序列为空，返回。

说到这里，就很明显了，这是一个递归。而且考虑一种情况，如果字符串是aa ， 那么就会出现aa ，aa 这样的答案，这样明显是不对的，所以我们添加一个结构，如果要交换的元素是相等的，那么我们就不交换了。

所以递归的代码如下：

void permutation(string str,vector<string>&res, int k)
{
    if(k == str.size()-1)
        res.push_back(str);
    sort(str.begin()+k,str.end());//把字符串排序，这样输出的字符串就是字典序的
    unordered_set<char> h;//用来记录已经交换的字符，如果重复不再交换
    for(int i=k;i<str.size();++i)
    {
        if(h.find(str[i]) == h.end())
        {
            h.insert(str[i]);
            swap(str[k],str[i]);//交换，进入新的排列
            permutation(str,res,k+1);
            swap(str[i],str[k]);//交换回来这个k，头部继续和剩下的后面交换
          }
      }
}

vector<string> Permutation(string str)
{ 
    vector<string> res;
    if(str.empty())
        return NULL;
    else
        permutation(str,res,0);
    return res;
}