46. Permutations

Question: Permutations

Solution

想法：

• 如果選 1，後面可以選 2 或 3
• 如果選 2，後面可以選 1 或 3
• 如果選 3，後面可以選 1 或 2

代表選了一樣 element 後，要再去 list 遍歷一遍，把「沒有」選過的 element 選進來

所以要有一個地方紀錄「選過的」 element，如果選過就跳過

• 終止條件：

  有一個地方紀錄目前選了哪些 element，當選到長度與 list 相同時，就把結果加入 result

• 遞迴條件：

  permute list 加入一個 element，進入遞迴繼續加入下一個 element，等到第一個 element 的所有可能解都找完後，將 permute list 回復原狀，pop 掉第一個 element

class Solution:

def permute(self, nums: list[int]) -> list[list[int]]:

res = list()

path = set()

per = list()

def dfs():

if len(per) == len(nums):

res.append(per.copy())

return

for i in range(len(nums)):

if nums[i] not in path:

per.append(nums[i])

path.add(nums[i])

dfs()

path.remove(nums[i])

per.pop()

dfs()

return res

Video Solution