1.给定一个数组，数组中元素均不相同，写出数组元素的全排列组合

比如： 
[1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

由于数组中不含相同元素，所有不用考虑重复问题，现在我们来解析 [1,2,3]的全排列是如何得到的：

1,2,3的全排列，我们先看后两个数[2,3]的全排列,很明显是2,3 和3,2，分别以2开头和3开头

然后看[1,2,3]的全排列，分别为1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们是以1开头和2,3全排列的组合，

以2开头1,3,全排列的组合，以3开头1,2,全排列的组合

也就是说我们可以将三个数的全排列问题转化为两个数的全排列问题，方法是：将数组中的每一个数均与数组的第一位的数进行交换，然后对剩下的数进行全排列；每一次交换后要交换回去，因为每一次都是在[1,2,3]的基础上进行的

以[1,2,3]为例就是，数组中的每一个元素都与第一为元素进行交换，1与第一位元素交换，得1,2,3；然后交换回去，为下一次交换做准备

2与第一位元素交换，得2,1,3；

3与第一位元素交换，得3,2,1；

然后对于得到1,2,3；2,1,3；3,2,1问题就可以缩减为除去第一位后2,3； 1,3； 2,1的全排列，然后与第一位组合

而对于2,3的全排列，也可以使用同样的方法，分别将元素2,3与第一位元素进行交换，继续缩减问题，转化为1个元素的全排列问题，对于2,3就是2,3；3,2；然后转化为单元素3和2的全排列问题

                          1,2,3                   //原问题    
                     /      |      \
                1,2,3      2,1,3    3,2,1         //遍历数组将数组元素分别与第一位元素交换，缩减问题为两个数的全排列问题,将问题缩减为了[2,3];[1,3];[2,1]的全排列问题
               /    \     /    \     /     \
         1,2,3  1,3,2  2,1,3  2,3,1 3,2,1  3,1,2 //遍历数组[2,3]，将数组元素分别与第一位元素交换，将问题缩减为1个数的全排列问题，即将问题缩减为[2]和[3]的全排列问题；其他数组[1,3];[2,1]类似处理
            |     |      |      |    |       |
         1,2,3   1,3,2  2,1,3  2,3,1 3,2,1  3,1,2 //可以继续这一步，也可以不继续，就是i = nums.size() 和nums.size()-1的区别

所以明显看出可以用深度优先搜索解决，因为每一步所做的处理是相同的

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) 
    {
        int len = nums.size();
        vector<vector<int>> res;
        DFS(nums,0,res);
        return res;
    }
private:
    void DFS(vector<int>&nums,int i,vector<vector<int>>& res)
    {
        if(i == nums.size())//因为每一次交换就可以将问题缩减一级，所以nums.size()次交换就可以将问题缩减为0级，0个数的全排列问题，问题最终得到解决，当然缩减到1级也是可以的（就是没有了最后自身与自身的交换而已）
        {
            res.push_back(nums);
            return;
        }
        for(int j = i; j < nums.size();j++)//遍历数组，分别将每一位元素与当前数组首位元素交换
        {
            swap(nums[i],nums[j]);//通过交换来实现全排列
            DFS(nums,i+1,res);
            swap(nums[i],nums[j]);//进行下一次交换时，是在原数组的基础上进行的，所以必须把首位元素交换回来
        }
        return;
    }
    
    
};

2.给定一个数组，数组中元素可以相同，写出数组元素的全排列组合，组合中不可以出现相同的排列

例如：
Input: [1,1,2,2]
Output:
[[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]

我们先来简单分析一下，仍然采用缩减问题的方法，遍历数组中每一个元素与第一个元素交换，得到四个数组

 [1,1,2,2];[1,1,2,2];[2,1,1,2];[2,1,2,1]我们发现缩减的问题有重复，有些缩减的问题是不可取的（重复），所以我们在交换之前要判断一下，该元素交换后的数组是否已经出现过，出现过则是重复问题，要舍弃；

所以在遍历元素与数组首元素交换时要判断是否已经出现过重复的结果，那么如何判断呢？

在[1,1,2,2]为一般性，我们用 i 代表数组首元素的下标，j 遍历数组元素时元素的下标，由于均与第一个元素交换，所以我们可以尝试着将第一个元素作为标志位，[1,1,2,2] i = 0,j =0时交换为[1,1,2,2];此时标志位为首元素1，就是说如果后面遍历的元素中再出现1，则与i=0 处的元素相交换后会产生重复（就是 i = 0,j = 1,这种情况，交换过后结果为[1,1,2,2]，重复，所以这种情况应该舍去）；当i =0,j = 2时，与标志位1不等，所以可以交换，为[2,1,1,2]，此时首元素位置处为2，标志位更新为2；这样就可以避免首元素为2的重复，(注，这里与上面不含重复元素的数组的全排列的不同之处在于，它交换后并不交换回来，而是在交换的基础上进行下去，当然这样的目的是为了避免重复)

而且这样做的前提是，数组中的元素必须按大小进行排列，否则

if(i != j && nums[i] == nums[j])
{
    continue;
}

不能剔除掉所有的重复排列；而且由于交换后不交换回来，而且要保持  遍历数组时的连续性（即这一次遍历交换在上次遍历交换的基础上进行，其实就是为了保留本次的标志位），所以程序中用的是指传递，而不是引用

这样在交换[1,1,2,2]中的第2个元素与首元素标志位后，就变为了[2,1,1,2]，之后在[2,1,1,2]的基础上进行判断，而不再采用[1,1,2,2];

如果用引用，则由于每一次都是深度优先搜索，中间有很多次交换性，如果交换后不交换回来，则会破坏数组元素的有序性，如果交换后交换回来，则每一次又都会在[1,1,2,2]的基础上进行，而不会保留上一次的标志位

完整程序如下：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        int len = nums.size();
        if(len == 0)
        {
            return res;
        }
        
        DFS(nums,0,res);
        return res;
    }
private:
    void DFS(vector<int> nums,int i ,vector<vector<int>> & res)
    {
        if(i == nums.size())
        {
            res.push_back(nums);
            return;
        }
        for(int j = i;j < nums.size();j++)
        {
            if(j != i && nums[i] == nums[j])
            {
                continue;
            }
            swap(nums[i],nums[j]);
            DFS(nums,i+1,res);   
        }
    }
};

3.下一个排列

在这个问题中我们不在要求求出所以元素的全排列，而只是想知道按字典比当前排列大的最近的排列是什么，如果当前排列已经是最大排列，则给出最小排列

比如

1,2,3 → 1,3,2  //1,3,2是比排列1,2,3大的最近的排列
3,2,1 → 1,2,3  //3,2,1已经是最大排列，所以转写为最小排列 1,2,3
1,1,5 → 1,5,1  //1,5,1 是比排列 1,1,5大的最近的排列

为简单起见先考虑整数，

比如   123 ，我们想要求由这三个数字组成比它大的最近的元素我们会怎么做，由于要求比123大且差值最小，所以能不动百位数1就不动1，由于个位数3比十位数3大，所以交换后132 > 123;符合要求

那么 1243 呢？秉承原则，高位能不动就不动，而且只能操作该位本身和低于它的位，从十位入手，由于4>3,所以不能动十位（因为4，3交换后变小），而2<4所以可以通过调整百位来使其增大，为了使其增大的最小，我们应该在4,3中选择一个比2大且差值最小的数，应选择3，同时十位和个位数应该按升序排列（由于在1243中，找到百位2时才满足高位小于低位，所以从十位到个位是降序排列的，只要对其进行反转即可），这样才能使其增大但增大的最少。

再以 56486431为例进行说明，由于 1 < 3, 3 < 4所以任意交换个十百位均只能使其减小，继续比较 4<6,6<8,8>4，所以可以调整4所在的这一位，在比4这一位低的位中进行查找大于4但差值最小的数，明显是6，与之交换，变为 56 684431，我们发现交换完毕后，6之后的数明显是降序排列，所以我们对其进行翻转就可以得到我们的目标数，56 613448，这就是比56486431大但差值最小的数，也是这几个数的全排列

完整程序如下：需要先进行相邻位的比较，找到需要调整的位，然后在比该位低的位中找一个比该位处的数大但差值最小的数，交换两者，然后将该位之后的元素进行翻转

class Solution {
public:
    void nextPermutation(vector<int>& nums) 
    {
        //寻找应该被交换的点
        int i = nums.size()-2;
        while(i >= 0 && nums[i+1] <= nums[i])//找到需要调整的位。如果该数组元素排列已经是最大值，则 i = -1;最后将数组全部翻转即可
        {
            i--;
        }
        if(i >= 0)
        {
            int j = nums.size()-1;
            while(i >= 0 && nums[j] <= nums[i])//找到比需要调整位处的数大但查找最小的数
            {
                j--;
            }
            swap(nums[i],nums[j]);//交换两者
            
        }
        reverse(nums.begin()+i+1,nums.end());//翻转
    }
};

使用递归的方法解决全排列问题

全排列的本质：对于一个字符串，递归的令每一个元素与其后面的每一个元素交换。

或者可以理解为

例如字符串abc：先观察第一个元素a，将a分别与b，c交换 得到bac  cba

                            再对于abc, bac, cba  观察第二个元素，与 第三个元素交换得 acb, bca, cab

                            所以abc的全排列为 abc, bac, cba, acb, bca, cab

若是字符串中有重复元素，那么 需要判断在一个元素与所有后续元素的交换过程中，有没有重复的元素即将被交换，如果有的话则跳过这次交换。

代码如下：

#include <iostream>
// 有重复元素的全排列
using namespace std;

// 全排列的总个数
int Num = 0;

void swap(char &a, char &b) {
    char temp;
    temp = a;
    a = b;
    b = temp;
}

// 判断s[i]的值是否在s[cur]~s[i]中出现过
bool no_same(char* s, int cur, int i){
    // 如果s[cur]的值在前面出现过，那么若s[cur]参与交换就会产生相同的排列
    for(int k = cur; k < i; ++k){
        if(s[i] == s[k]){
            return false;
        }
    }
    return true;
}

void full_per(char* s, int cur, int len){
    // 终止条件：当前参与交换的是最后一个元素
    if(cur == len-1){
        // 输出一个排列
        for(int i = 0; i < len; ++i){
            cout << s[i];
        }
        cout << endl;
        Num++;
    }
    // 递归实现：当前cur元素与后面的每一个元素交换
    for(int i = cur; i < len; ++i){
        // 如果s[cur]没有出现过，进入递归交换
        if(no_same(s, cur, i)) {
            swap(s[i], s[cur]);
            full_per(s, cur + 1, len);
            // 换回来，保证交换的有序进行
            swap(s[i], s[cur]);
        }
    }
}

int main() {
    int n;
    cin >> n;
    char s[20];
    cin >> s;
    // 计算字符数组长度，减去回车和结束符
    full_per(s, 0, n);
    cout << Num << endl;
    return 0;
}

使用字典序的方法解决全排列问题

先求出最小串如 “123456” 显然最大串为“654321”

字典序全排列的原理：生成的下一个排序恰好比当前排列大，由此从小到大生成的排序集合一定是全排列。

显然，使用字典序可以直接排除重复元素的问题。

参考：https://zh.wikipedia.org/wiki/%E5%85%A8%E6%8E%92%E5%88%97%E7%94%9F%E6%88%90%E7%AE%97%E6%B3%95

输入一个字符串（可能有重复字符），输出该字符串中所有字符的全排列。
示例：
输入：s = "abb"
输出：["abb","bab","bba"]
题目来源：LeetCode 剑指 Offer 38. 字符串的排列

思路

1. 首先对给定字符串排序，使相同的字符排在一起；
2. 利用回溯法，搜索出所有可能的情况；
3. 剪枝，如果当前位置的字符和上一位置的字符相同，且上一字符已被选，此情况跳过，实现去重；
4. 本篇利用的是位运算记录字符是否被选中。

代码

class Solution {
public:
    void dfs(int u, int n, vector<char>& cur, string s, vector<string>& ans, int pos) {
        if (u == n) {
            string res = "";
            for (char c : cur)
                res += c;
            ans.push_back(res);
            return;
        }
        
        for (int i = 0; i < n; i ++ ) {
            if (i && s[i] == s[i - 1] && (pos >> (i - 1) & 1)) continue; //相同且上一字符被选
            if ((pos >> i) & 1) continue; //当前字符被选
            cur.push_back(s[i]);
            dfs(u + 1, n, cur, s, ans, pos | (1 << i));
            cur.pop_back();
        }
    }

    vector<string> permutation(string s) {
        sort(s.begin(), s.end());
        vector<string> ans;
        int n = s.size();
        vector<char> cur; //当前已选中的字符
        dfs(0, n, cur, s, ans, 0);
        return ans;
    }
};