題目出處
難度
medium
題目分類
Array, Backtracking
2026-08-17 二刷
個人範例程式碼 - 二刷 (2026/08/17)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
used = [False] * len(nums)
path = []
def backtrack():
if len(path) == len(nums):
ans.append(path[:])
return
for i, num in enumerate(nums):
if not used[i]:
used[i] = True
path.append(num)
backtrack()
used[i] = False
path.pop()
backtrack()
return ans
算法說明
Time Complexity
O(n*n!)
說明：n! 來自於數學的排列本來就是 n! 種組合，n 來自於複製陣列會需要遍歷一次當前 Path 的狀態。
Space Complexity
O(n) # 用來儲存 path 的長度，其餘 ans, used 所需要的空間也沒有造成空間數量級的增加
Boundary conditions
- [1] 留意會不會沒辦法處理單個項目
- [0, 1] 留意有沒有重複結果的問題
2022-04-24 一刷
個人範例程式碼 - 一刷 (2022/04/24)
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return nums
self.ans = []
self.dfs(nums, [])
return self.ans
def dfs(self, nums, permutations):
# end of recursion
if not nums:
self.ans.append(list(permutations)) # deepcopy
return
# define and split
for i, num in enumerate(nums):
permutations.append(num)
# temporarily remove element i = start[0:i] + start[i+1:]
self.dfs(nums[:i] + nums[i+1:], permutations)
permutations.pop() # backtracking
算法說明
排列類型的題目，使用 dfs 去搜尋全部的結果，
另外在處理順序時，我們使用傳入「start[0:i] + start[i+1:]」的方式，暫時移除了 start[i] 的元素，
這樣的操作方式會複製一個新的 list，而不會影響到原本的 list
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
當沒有 nums 時，return nums
Boundary conditions
搜尋至 no nums 時，添加結果回傳 (表示元素已使用完畢)