一、題目介紹
今天要練習的是LeetCode 46：Permutations（全排列）

題目給定一個沒有重複元素的整數陣列nums，要求找出所有可能的排列方式

例如：nums = [1, 2, 3]
所有排列為：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

如果陣列有 n 個元素，總排列數會是：n!
例如：3! = 3 × 2 × 1 = 6
所以這題會比 Day 23 的 Subsets 更需要注意「目前哪些元素已經被使用」

二、解題想法：Backtracking
這一題使用 Backtracking（回溯）

可以把它想成：每一次從還沒有使用過的數字中選一個，放進目前的排列中

例如：[1, 2, 3]

第一層可以選：
1
2
3

如果第一個選 1，下一層就只能從2、3裡面選
如果接著選 2：[1,2]
最後只能選 3：[1,2,3]
完成後回到上一層，把 2 移除，再嘗試：[1,3,2]

這就是回溯的核心：選擇 → 繼續探索 → 撤銷選擇 → 嘗試下一個選項

三、為什麼需要used？
這題和 Day 23 的 Subsets 有一個很大的不同
Day 23：[1,2,3]
我們使用start控制只能往後選

但Permutations不一樣
例如我們已經選[1]
下一步可以選2 或 3
但是不能再選1
因此需要一個used陣列，記錄每個元素目前有沒有被使用

例如：
nums = [1,2,3]
used = [true, false, false]

代表：
1 → 已使用
2 → 尚未使用
3 → 尚未使用
當排列完成後，就開始回溯，把使用狀態恢復

四、Java實作

五、Python實作

六、時間與空間複雜度
假設共有n個元素

時間複雜度：O(n × n!)

• 總共有n!
• 而每個排列還需要花費O(n)複製到結果中

空間複雜度

• 遞迴深度最多為n，另外使用used陣列：O(n)
• 如果把最後儲存所有答案的空間也算進去，則需要：O(n × n!)

七、Java與Python比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天的Permutations讓我更熟悉Backtracking（回溯）的概念。和前一天的Subsets相比，這一題不是單純決定「要不要選某個元素」，而是要考慮每個元素在目前排列中是否已經使用過，因此需要透過used陣列來記錄狀態。

一開始看到排列問題時，可能會覺得要自己把所有順序列出來非常麻煩，但使用回溯之後，可以讓程式自動探索每一種可能性。每當一組排列完成，就先把答案保存下來，再撤銷上一個選擇，繼續尋找其他可能。

這次也讓我更理解回溯中的「撤銷選擇」為什麼重要。如果只加入元素，卻沒有pop()或重新設定used，程式就無法正確嘗試其他排列。

透過Java和Python同時實作，我也發現兩種語言雖然語法不同，但演算法本身並沒有改變。只要先理解「選擇、探索、回溯」的流程，就能將同一個想法轉換成不同程式語言。