📘 題目敘述
給定一個由互不相同整數組成的陣列 nums，請回傳它的所有排列。
答案可以用任意順序回傳。
條件限制
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中所有整數都互不相同
🧠 解題思路（一）直接遞迴
我這題是直接寫遞迴函數。
我的想法是先假設：
- 前
n - 1個數字的所有排列我都已經知道了
那我現在只要把第 n 個數字，插進這些排列的每一個可能位置，就能得到前 n 個數字的所有排列。
所以這題的遞迴核心就是：
- 先遞迴求出
n - 1個數字的所有排列 - 再把第
n個數字插入每個排列的每個位置
這樣一路往上組回來，就能得到全部答案。
所有變數
ans：目前這一層遞迴要回傳的所有排列v：遞迴求出來的n - 1個數字的所有排列now：目前這一層要插入進去的新數字x：某一個較小規模的排列y：把now插入某個位置之後形成的新排列
🪜 主要流程步驟（一）
1. 先定義遞迴函式的意義
我把遞迴函式 f(n, nums) 定義成：
- 回傳
nums前n個元素所形成的所有排列
也就是說：
f(1, nums)會回傳只有一個數字時的排列f(2, nums)會回傳前兩個數字的所有排列- ...
f(n, nums)就是我要的完整答案
這樣整個遞迴結構會很清楚。
2. 先處理遞迴的 base case
如果 n == 1，那就代表目前只剩一個數字。
只有一個數字時，排列就只有一種，所以我直接回傳：
return {{nums[0]}};
這就是整個遞迴往上展開時的最基本起點。
3. 先遞迴求出前 n - 1 個數字的所有排列
如果 n 不等於 1，我就先遞迴去算：
v = f(n - 1, nums);
這代表我先拿到前 n - 1 個數字的所有排列結果。
接著我再把第 n 個數字加進去。
我這裡用：
int now = nums[n - 1];
把這一層要新加入的數字記下來。
4. 把 now 插進每個舊排列的每一個位置
這題最核心的地方就是這一步。
對於 v 裡面的每一個排列 x，我都把 now 插進去所有可能的位置：
- 插在最前面
- 插在中間
- 插在最後面
這段意思是：
x是某個已經排好的n - 1長度排列- 我複製一份成
y - 再把
now插入第i個位置 - 這樣就會得到一個新的長度
n排列 - 最後把它放進
ans
因為一個長度 n - 1 的排列，總共有 n 個位置可以插入新數字，
所以每個舊排列都能產生 n 個新排列。
5. 把這一層組好的所有排列回傳
當我把 now 插進所有舊排列的所有位置之後，ans 裡面就會放著前 n 個數字的全部排列。
這樣就能把結果回傳給上一層遞迴。
6. 主函式只要呼叫完整規模的遞迴
在主函式 permute 裡，我先取出陣列長度 n，然後直接回傳：
return f(n, nums);
因為 f(n, nums) 的定義本來就是「前 n 個數字的所有排列」，
所以這裡就剛好是整題答案。
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n \cdot n!)
共有n!個排列，而每次建立新排列時還會有插入與複製成本，所以整體可以記成O(n \cdot n!)。 - 空間複雜度：
O(n \cdot n!)
需要儲存所有排列結果。
💻 程式碼實作（一）
class Solution {
public:
vector<vector<int>> f(int n, vector<int>& nums) {
if (n == 1) {
return {{nums[0]}};
}
vector<vector<int>> ans;
vector<vector<int>> v = f(n - 1, nums);
int now = nums[n - 1];
for (auto& x : v) {
for (int i = 0; i < n; i++) {
auto y = x;
y.insert(y.begin() + i, now);
ans.push_back(y);
}
}
return ans;
}
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
return f(n, nums);
}
};
🧠 解題思路（二）回溯寫法
我這份寫法是用標準 backtracking。
我的想法是從空的排列開始，一個位置一個位置往下填。
每次都去找目前還沒用過的數字，把它加進 now，然後遞迴處理下一層。
當 now 的長度已經等於 n 時，就代表已經湊出一個完整排列了，直接放進答案。
這種寫法的重點就是：
now記目前正在組的排列check[i]記nums[i]有沒有用過- 每次遞迴結束後要把狀態還原，讓下一個選擇可以繼續試
所有變數
ans：最後要回傳的所有排列now：目前正在組的排列check：記錄每個位置的數字是否已經被使用過n：陣列長度
🪜 主要流程步驟（二）
1. 先把遞迴要用的狀態準備好
我把幾個會在整個 backtracking 過程中一直用到的東西直接寫成成員變數：
ans：存所有答案now：存目前路徑check：存使用狀態n：存陣列長度
這樣遞迴函式 f 裡面就不用每次都一直傳很多參數，寫起來會比較直接。
2. 遞迴函式的目標是把目前排列一路填滿
我寫的 f(nums)，它的意思是：
- 以目前
now的狀態為基礎 - 繼續往下填還沒選過的數字
- 直到形成一個完整排列
所以每一層遞迴，其實都在做同一件事：
- 枚舉還沒用過的數字
- 選一個放進
now - 然後繼續遞迴
3. 如果 now.size() == n，代表已經得到一組完整排列
這是遞迴的終止條件：
if(now.size()==n){
ans.push_back(now);
return;
}
當 now 的長度已經和 n 一樣時，就表示：
- 每個位置都填好了
- 而且每個數字都只用了一次
所以這時候 now 就是一組合法排列，直接放進 ans 裡即可。
4. 每一層都去枚舉所有還沒被使用的數字
如果目前排列還沒填滿，我就用一個迴圈把所有數字都試一遍：
- 如果
check[i]已經是true，代表nums[i]之前已經被放進now了 - 那這一層就不能再用它，所以直接跳過
- 只有還沒用過的數字，才可以拿來當目前這一格的候選答案
5. 選一個數字放進去，遞迴完再還原狀態
當我決定要選 nums[i] 時，就先做三件事：
check[i]=true;
now.push_back(nums[i]);
f(nums);
也就是：
- 先標記這個數字已經使用過
- 把它加到目前排列
now的尾端 - 然後遞迴去處理下一層
等遞迴回來之後，還要把剛剛的選擇取消掉：
now.pop_back();
check[i]=false;
這一步很重要，因為 backtracking 的核心就是：
- 試一個選擇
- 做到底
- 回來之後把現場恢復
- 再試下一個選擇
如果不把狀態還原，後面的分支就會被前面做過的選擇污染。
6. 主函式先初始化，再呼叫遞迴
在 permute 裡，我先把 n 記下來，然後把 check 開成長度 n、初始值全是 false：
n=nums.size();
check.resize(n,false);
這表示一開始所有數字都還沒被用過。
接著直接呼叫：
f(nums);
讓遞迴從空排列開始慢慢展開。
最後回傳 ans，就是所有排列。
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n \cdot n!)
總共有n!種排列，而每一組排列建立過程都和長度n有關。 - 空間複雜度：
O(n \cdot n!)
需要儲存所有排列結果；另外遞迴深度和暫存路徑是O(n)。
💻 程式碼實作（二）
class Solution {
public:
vector<vector<int>> ans;
vector<int> now;
vector<bool> check;
int n;
void f(vector<int>& nums) {
if(now.size()==n){
ans.push_back(now);
return;
}
for(int i=0;i<n;i++){
if(check[i]){
continue;
}
check[i]=true;
now.push_back(nums[i]);
f(nums);
now.pop_back();
check[i]=false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
n=nums.size();
check.resize(n,false);
f(nums);
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/permutations/