小旭讲解 LeetCode 40. Permutation
小旭讲解 LeetCode 40. Permutation

题目

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/
0 0 vote
Article Rating
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

[…] 小旭讲解 LeetCode 46. 全排列 […]