46. 全排列

前置題目：78. 子集, 90. 子集 II
相似題目：消滅怪物

思路

現在想要一個數組的所有排列方式，像是[1,2,3]就有六種排列。
最初的數組是一種排列，可以用它去拓展出所有排列方式。
dfs(i)代表當前要嘗試的位置，這個位置需要嘗試自己位置之後，所有可能的數字，

• dfs(0)，此時三個數字[1,2,3]都沒選過，第一個位置可以更換為[1,2,3]任意一個數字。假設選2。這時數組變成[2,1,3]，再去呼叫dfs(1)。
• dfs(1)這時能選的數字剩兩個，[1,3]，在裡面選一個，假設選[3]，數組[2,3,1]，呼叫dfs(2)。
• dfs(2)只能選一個數字，數組[2,3,1]，呼叫dfs(3)，終止條件。

在這個過程中，呼叫dfs(i)，還沒被選中的數字就是i位置以後的數字，並且在選完之後，要將現場還原，否則對於上一層而言，「還沒被選中的數字」會亂掉。

• 當我在狀態 A 時要做出多個操作，就需要確保每次操作時，我的狀態都沒有變化。
  • 我操作時，將狀態 A 改成 B 後呼叫遞迴，遞迴結束就應該依舊是狀態 A，所以最後再改回狀態 A。
  • 再次操作，將狀態 A 改成 C 後呼叫遞迴，遞迴結束後應該依舊是狀態 C，所以最後再改回狀態 C。
  • 操作完畢，終止時應該也要是狀態 A。

關於為什麼要還原，看影片會清楚非常多。www.bilibili.com

程式碼

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        auto dfs = [&](this auto&& dfs, int i) -> void {
            if(i == n) {
                res.push_back(nums);
            }
            else {
                for(int j = i; j < n; ++j) { // 每次選擇後面的其中一個數字, 跟現在所在的位置交換
                    swap(nums[i], nums[j]);
                    dfs(i + 1);
                    swap(nums[i], nums[j]); // 還原現場
                }
            }
        };
        dfs(0);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\times{n!})$
• 空間複雜度：$O(n)$