【LeetCode】46.全排列（回溯算法）

一、題目描述

給定一個 沒有重複 數字的序列，傳回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]      

二、解題思路 & 代碼

def permute(nums):
    res = []
    def backtrack(nums, tmp):
        if not nums:
            res.append(tmp)
            return
        for i in range(len(nums)):
            backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])
    backtrack(nums, [])
    return res


if __name__ == '__main__':
    nums = [1,2,3]

    print(permute(nums))

    # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]      

1. 時間複雜度：，其中 n 為序列的長度
2. 空間複雜度：，其中 n 為序列的長度。除答案數組以外，遞歸函數在遞歸過程中需要為每一層遞歸函數配置設定棧空間，是以這裡需要額外的空間且該空間取決于遞歸的深度，這裡可知遞歸調用深度為 。

參考：

1. ​​LeetCode題解​​