題目要求

要求在給定的一個 沒有重復 數字的序列，返回其所有可能的全排列。

圖解示例

算法思想

使用遞歸的方法

設計全局變量（也就是返回值），設計存儲分步結果的列表，設計一個數組，用來判斷該數是否已經在分步結果中

特判，如果傳入的是一個空列表，那返回空列表

開始設計遞歸函數

根據 題目要求 和 圖解示例

設置遞歸邊界，若層數與列表容量 len 相等，即列表中的所有值都在分步結果 result 中了，然后將 result 加入 ans中

如圖解示例所示，遍歷整個數組，得到 layer = 1 的情況下，分步數組的值

如果這個值沒有被訪問過，那么把這個值放入分步結果 result 中，并將標記數組中該值的位置定義為 true

得到這一狀態下的值 layer = 1 之后，進入 layer = 2 的狀態

當一串遍歷返回之后，就將標記數組中該值的位置定義為 false，對之后的其他結果遍歷不造成影響

最后將該值從 result 中 pop 出來

我將每一步遞歸都打出來，更方便大家理解

完整代碼

class Solution { public:vector<vector<int> > permute(vector<int>& nums) {int len = nums.size();if (len == 0) {return ans;}vector<int> result;bool flag[len] = {false};findPermute(0, result, nums, len, flag);return ans;} private:vector<vector<int> > ans;void findPermute(int layer, vector<int> result, vector<int>& nums, int len, bool flag[]) {if(layer==len){ans.push_back(result);return;}for(int i = 0; i < len; i++) {if(!flag[i]) {result.push_back(nums[i]);flag[i] = true;findPermute(layer+1, result, nums, len, flag);flag[i] = false;result.pop_back();}}} };

設計分析

時間復雜度：O(n * n!)（數數圖解的箭頭吧！）

空間復雜度：O(n)

提交結果

若有其他解法，歡迎評論區補充。

總結

以上是生活随笔為你收集整理的【LeetCode】0046.全排列 (递归详解)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。