题解 | 全排列

题干分析

题目给定我们一个内部元素各异的数组,要求我们排列数组中的元素,并将所有排列方式存在线性表中返回.

算法思路

• 我们在学习排列组合时便考虑过如何获得一列各项不同的元素的全排列数:即n!,因为我们首先需要确定第一个数排谁,此时有n个选择,在确定第二个,此时有n-1个选择,因为它前一个数已选,不能再选...依此类推.
• 由此我们直接采用递归模拟这个过程即可.

实现代码

class Solution {
    int n = 0;
    vector<vector<int> > ans;
    vector<int> tmp;
    vector<bool> vis;

    void dfs(const int idx, vector<int> &nums) {
        if (idx == n) ans.push_back(tmp);
        else {
            for (int i = 0; i < n; ++i) {
                if (!vis[i]) { // 此前未选
                    tmp[idx] = nums[i];
                    vis[i] = true; // 标记已选
                    dfs(idx + 1, nums);
                    vis[i] = false; // 撤销选择
                }
            }
        }
    }

public:
    vector<vector<int> > permute(vector<int> &nums) {
        n = static_cast<int>(nums.size());
        tmp.resize(n);
        vis.resize(n);
        dfs(0, nums);
        return ans;
    }
};

复杂度分析

• 时间复杂度: 递归进行排列,时间复杂度如算法思路所述O(n!),每次排列完成后还需要复制长度为n的数组,共计n!次复制,时间复杂度为O(n * n!),总结O(n * n!).
• 空间复杂度: 递归深度最高为n,调用栈空间消耗为O(n),其他辅助空间也为O(n),总计为O(n).