给出1到n的这n个数的全排列，其类似的问题在acwing上和leetcode有四道题，分别是

leetcode 46.全排列
leetcode 47.全排列ii
AcWing 1537 .递归实现排列类型枚举 II
AcWing 94. 递归实现排列型枚举

4道题可以分为两大类，集合中

• 无重复元素
• 有重复元素

总体思路大体为 DFS + 回溯：

两种思考模式 ：
1） 每个位置上放什么数
2）每个数应该放在那个位置 。 这里我们考虑前者，其步骤为

• 依次枚举每个位置
• 每个位置上选择一个还未被使用的数

先从最简单的没有重复的情况来看

AcWing 94. 递归实现排列型枚举

题意

把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序，要求按照字典序升序的顺序输出

样例

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

c++代码

#include <iostream>

using namespace std;

const int N = 10;

int n;
int nums[N];
bool st[N];  // 记录该数又没用被使用过

void dfs(int u)
{
    if (u > n)  // 数选够了，可以返回了
    {
        for (int i = 1; i <= n; i ++ ) printf("%d ", nums[i]);
        puts("");
        return;
    }

    // 枚举该位置上放的数，该数之前并未使用过
    for (int i = 1; i <= n; i ++ )  // 从小到大枚举树，输出一定满足字典序升序
        if (!st[i])
        {
            nums[u] = i;  
            st[i] = true;
            dfs(u + 1);    // 枚举下一个位置
            st[i] = false; // 回溯修改现场
        }
}

int main()
{
    scanf("%d", &n);

    dfs(1); // 第1个位置选什么数

    return 0;
}

与其相关的leetcode 46.全排列

题意

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

样例

输入:

[1,2,3]

输出:

[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

c++ 代码

• 注意dfs() 是从0 开始递归的哈

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permute(vector<int>& nums) {
        st = vector<bool> (nums.size());
        dfs(nums, 0);    // 从第一位位置开始选， 注意我们从下标0开始作为起点
        return res;
    }

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

        for(int i = 0; i < nums.size(); i++)
        {
            if(!st[i])
            {
                path.push_back(nums[i]);
                st[i] = true;
                dfs(nums, u + 1);   // 下个位置选什么
                st[i]= false;
                path.pop_back();
            }
        }
    }
};

接下里有重复的情况，重点为怎么去重？

思路

• 把将所有数从小到大排序，这样相同的数会排在一起；
• 选择数的时候判断是否重复即可，重复的跳过

AcWing 1537 .递归实现排列类型枚举 II

题意

给定一个长度为 n 的可包含重复数字的序列，请你求出其所有不重复的全排列。

样例

输入样例：

3
1 1 2

输出样例：

1 1 2
1 2 1
2 1 1

c++ 代码

// 
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
int a[N], nums[N];
bool st[N];

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ )  printf("%d ",nums[i]);
        puts("");
        return;
    }
    // 枚举还未用过的数 记得最后人为跳过重复的数
    for (int i = 0; i < n; i ++ )
        if (!st[i])
        {
            nums[u] = a[i];
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
            while (i + 1 < n && a[i + 1] == a[i]) i ++ ; // 找到下一个不重复的数
        }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )  scanf("%d", &a[i]);

    sort(a, a + n); // 排序很重要

    dfs(0);

    return 0;
}

同理leetcode 47.全排列ii
题意同上，这里就省略了

c++代码

class Solution {
public:

    int n;
    vector<vector<int>> res;
    vector<bool> st;
    vector<int> path;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        st = vector<bool>(n);

        sort(nums.begin(), nums.end());  // 排序很重要

        dfs(nums, 0);

        return res;
    }

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

        for (int i = 0; i < n; i ++ )
            if (!st[i])
            {
                st[i] = true;
                path.push_back(nums[i]);
                dfs(nums, u + 1);
                path.pop_back();
                st[i] = false;
                while (i + 1 < n && nums[i + 1] == nums[i]) i ++ ;  // 跳过重复的数
            }
    }
};

拓展

• 如何用每个数应该放在哪个位置这么模式来思考？
• 如何用迭代的方式来写？

参考资料

[LeetCode暑期刷题打卡2019——Week5 DFS+回溯] (https://www.bilibili.com/video/BV1M4411Q7td)