小旭讲解 LeetCode 46. 全排列

题目

思路

经典的排列问题，它主要借助递归函数去搜索。搜索的过程，类似于在一棵多叉树上进行。当遇到叶子节点时，即找到了一条合法的搜索路径。此时，需要跳出递归函数（栈），返回到上一层（即回溯的特性），进行搜索另一条分支路径，直到全部搜索完毕。

代码

class Solution {
public:
    void dfs(vector<int>& nums, vector<int>& vis, vector<vector<int>>& rs, vector<int>& r) {
        if (r.size() == nums.size()) {
            rs.push_back(r);
            return;
        }
        for (int i=0;i<nums.size();++i) {
            if (vis[i]) continue;
            vis[i]=1;
            r.push_back(nums[i]);
            dfs(nums,vis,rs,r);
            r.pop_back();
            vis[i]=0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        int n=nums.size();
        vector<int> vis(n,0);
        vector<vector<int>> rs;
        vector<int> r;
        dfs(nums, vis, rs, r);
        return rs;
    }
};

复杂度分析

Time： $O(n * n!)$ n for nums.length，dfs 共有 n 层，第一层的合法选择是n，第二层的合法选择是 n – 1，…，第 n 层的合法选择是 1，故有 n! 级别次 dfs 函数的调用。可知，其方案数是 n！。每一种方案都需要将结果集 r 追加到 rs中，其复杂度是 $O(n)$ ，故总体复杂度为 $O(n * n!)$
Space: $O(n)$ 递归调用（栈）的深度

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-tutorial-leetcode-46-permutation/