今天是紀錄LeetCode解題的第四十六天

第四十六題題目：Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

給定一個包含不同整數的數組nums，回傳所有可能的排列，可以按任意順序回傳

解題思路

這題相當的簡單，用回溯法，遍歷整個nums，如果nums[i]還沒被使用過就新增到path裡，否則就回溯找其他組合

程式碼

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        used = [False] * len(nums)
        result = []
        dfs(nums,used,[],result)
        return result
def dfs(nums,used,path,result):
    if len(path) == len(nums):
        result.append(path[:])
    for i in range(len(nums)):
        if not used[i]:
            used[i] = True
            path.append(nums[i])
            dfs(nums,used,path,result)
            used[i] = False
            path.pop()

以範例一來說，執行過程會先把1加到path裡，接著進到下一次遞迴，每一次遞迴時i都是從索引0開始，但索引0(值1)已經被使用過，所以把沒有使用過的索引1(值2)加到path裡，再進到下一次遞迴，同理這此把索引2(值3)加入path，再進到下一次遞迴，這一次path已經儲存找到的結果，把它加到result裡，接著i繼續遍歷nums，會發現數字全部都被使用過，此時回溯找其他組合