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());//翻转
    }
};

 

关于字符的全排列问题也是有很多算法的，今天我就来介绍递归的Perm算法。直接看题吧。。。

给定一字符串，可能含有相同元素。请借助递归设计算法求出该字符串的所有不同的排序。

输入格式：

给定一串字符串（长度小于等于9,且至少有3个字符相同）。

输出格式：

每行输出一个字符串。按照字典序递增的顺序输出，每个排列占一行。

最后一行输出不同排列的个数。

题目大体意思就是要我们求一个字符串的全排列，说到递归，那么Perm算法出来了，Perm算法核心思想是把m个待排元素每一个依次拿到首位，剩下的m-1个组成新的待排元素传入Perm进行相同的操作……….以此类推，直到元素递归到只有一个了，就依次打印出来 形成一个排列

先上算法的核心部分：



void Perm(char b[],int low,int high,int& n)//这里把待排序元素放入char型数组b中，待排元素起始下
                                      //标为low，末尾下标为high，n用来计有多少种不同的排列组合                                                            
{

    if(low == high)              //如果递归排到只有最后一个元素，就按序打印出来
    {
        for(int i = 0;i < low;i++)
        {
            printf("%c",b[i]);

        }
            n++;                  //打印一次计数值加1
        printf("\n");             //每打印一次排列就换一次行
    }
    else                         //如果传进来的待排字符不止一个字符
    {
        for(int i = low;i < high;i++)
        {

            swap(b[low],b[i]);     //把每个元素挨个拿到首部low的位置
            Perm(b,low+1,high,n);  //除拿到首部之外剩下的再进入Perm递归
            swap(b[low],b[i]);     //还原字符串为交换前的样子，以进行下个字符的交换
        }

    }
}

这只是Perm最原始思想的体现，目前还不具备处理重复元素的能力，比如aabc,把第一个a拿到首位和把第二个a拿到首位，再让其与字符进行全排列后的效果是一样的，因此，我们在交换前应该加一个判断，如果在该字符位置之前存在相同的字符，该字符就不进行多余的交换了，跳往下一个字符的判断，修改代码如下：

for(int i = low;i < high;i++)
        {
           if(isSwap(b,low,i)) //交换前判断之前是否有相同的元素被拿到首位过
           {        
            swap(b[low],b[i]);
            Perm(b,low+1,high,n);
            swap(b[low],b[i]);
           }
        }

当然了，到目前位置还存在的一个问题就是没有满足字典序打印的问题，由于该算法是一个元素一个元素输出的，所以没有办法在得到结果之后在进行排序，只得对算法本身加以调整，如下：



for(int i = low;i < high;i++)
        {
           sort(b+low,b+high);//把每次递归传进来的元素先排个序，用了sort库函数，它包含在在头文件<algorithm>中
           if(isSwap(b,low,i)) 
           {        
            swap(b[low],b[i]);
            Perm(b,low+1,high,n);
            swap(b[low],b[i]);
           }
        }

这样工作就都做完啦。。

这一题完整代码如下：



#include<iostream>

#include<algorithm>

using namespace std;

void swap(char& a,char& b)      //两个元素进行交换
{
    char c = a;
         a = b;
         b = c;
}

bool isSwap(char b[], int start, int i) //i为该元素下标
{
        for(int k = start; k<i;k++)   //判断在该元素之前有没有相同元素
            if(b[k] == b[i])
                return false;         //如果有，则返回false
        return true;
}
void Perm(char b[],int low,int high,int& n)  //核心的算法啦
{

    if(low == high)
    {
        for(int i = 0;i < low;i++)
        {
            printf("%c",b[i]);

        }
            n++;
        printf("\n");
    }
    else
    {
        for(int i = low;i < high;i++)
        {
           sort(b+low,b+high);
           if(isSwap(b,low,i)) 
           {        
            swap(b[low],b[i]);
            Perm(b,low+1,high,n);
            swap(b[low],b[i]);
           }
        }

    }
}

int main()
{
        int  n = 0;      //计数用的   
        string str;
        cin>>str;        //用字符串接收待排元素

        char b[9] ;
        int i = 0;
        while(str[i]!='\0')
        {
            b[i] = str[i];       //把待排元素装进字符数组中
            i++;    
        }
        Perm(b,0,str.length(),n); //调用Perm进行排序
        cout<<n<<endl;            //输出总排列个数  

} 

 M个元素中含有相同的元素，如何得到他们的全排列（不重复排列）？ 


元素表述：   a1,a1,...a1,   a2,a2,...a2,.......,an,an,...an 

  其中，a1的个数为N1,   a2的个数为N2,以此类推，总个数为M。 


则可以证明不重复的排列种类的数目:   M!/(N1!*N2!*...*Nn!) 

 
 就是将N个数字做全排列。不过对于某些数字不能选择而已。 

这里只要限制将要选择的数字必须大于原来已经选择的数字就可以达到目标。 

下面是递归算法 
#include <stdio.h> 
#define   N   5 


void   arrange(int   rec[],int   used[],int   depth); 
void   write(int   rec[],   int   maxdepth); 
int   a[N]={1,1,2,2,3};   //这些值必须升序排列且大于0 
int   count=0; 

int   main() 
{int   rec[N+1]={0},used[N+1]={0}; 
  
    arrange(rec,used,0);   
    printf( "\ncount=%d ",count); 
    getchar(); 
    return   0; 
}     

void   write(int   rec[]) 
{   int   i; 
    for(i=0;i <N;i++) 
          printf( "%4d ",a[rec[i]]); 
    printf( "\n "); 
    count++; 
} 

void   arrange(int   rec[],int   used[],int   depth) 
{ 
  int   i,found_num; 
    if   (depth> =N)   write(rec);   //找到了一个可行解，输出 
    else 
      {found_num=0;               //增加这个变量记录原来本结点存储的数字 
        for(i=0;i <N;i++)     //   搜索该结点的孩子结点   
        {//如果该下标在前面还没有使用过，且该下标所指示的数字比 
          //原先所放置的数字要大，则是一个部分解 
            if(used[i]==0   &&   a[i]> found_num   )   
            {   rec[depth]=i;       //记录下该结点放置的下标   
                found_num=a[i];   //记录下本结点存放的数字   
                used[i]=1;             //   标记该下标已经被使用 
                arrange(rec,used,depth+1);       //   扩展，进入孩子结点继续搜索   
                used[i]=0;           //退回来后要清除本结点所记录下标的使用记录 
            } 
        }     
    } 
}

全排列问题
含有重复数字的全排列问题
算法1
(回溯算法)  $O(n^2)$
由于有重复元素的存在，这道题的枚举顺序和 Permutations 不同。

先将所有数从小到大排序，这样相同的数会排在一起；
从左到右依次枚举每个数，每次将它放在一个空位上；
对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 start，我们在枚举当前数时，只枚举 start+1,start+2,…,nstart+1,start+2,…,n 这些位置。
不要忘记递归前和回溯时，对状态进行更新。

时间复杂度分析：搜索树中最后一层共 n! 个节点，前面所有层加一块的节点数量相比于最后一层节点数是无穷小量，可以忽略。且最后一层节点记录方案的计算量是$O(n)$，所以总时间复杂度是 $O(n×n!)$。
C++ 代码
class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>> ans;

    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size(), false);
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = start; i < nums.size(); i ++ )
            if (!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                if (u + 1 < nums.size() && nums[u + 1] != nums[u])
                    dfs(nums, u + 1, 0);
                else
                    dfs(nums, u + 1, i + 1);
                st[i] = false;
            }
    }

};


互不相同数字的全排列问题
算法1
(回溯算法)  $O(n*n!)$
我们从前往后，一位一位枚举，每次选择一个没有被使用过的数。

选好之后，将该数的状态改成“已被使用”，同时将该数记录在相应位置上，然后递归。

递归返回时，不要忘记将该数的状态改成“未被使用”，并将该数从相应位置上删除。
时间复杂度分析：搜索树中最后一层共 n! 个节点，前面所有层加一块的节点数量相比于最后一层节点数是无穷小量，可以忽略。且最后一层节点记录方案的计算量是$O(n)$，所以总时间复杂度是 $O(n×n!)$。
C++ 代码
class Solution {
public:
    vector<vector<int>> ans;
    vector<bool> st;
    vector<int> path;

    vector<vector<int>> permute(vector<int>& nums) {

        for (int i = 0; i < nums.size(); i ++ ) st.push_back(false);
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int> &nums, int u)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return ;
        }

        for (int i = 0; i < nums.size(); i ++ )
            if (!st[i])
            {
                st[i] = true;
                path.push_back(nums[u]);
                dfs(nums, u + 1);
                st[i] = false;
                path.pop_back();
            }
    }
};

当然也可以用stl库里面的函数next_permutation函数
class Solution {
public:
    vector<vector<int>>ans;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        do {
            ans.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return ans;
    }
};

参考

剑指offer
https://www.acwing.com/solution/LeetCode/content/124/