題目：

給定不含重復數字的數組nums,返回其所有可能的全排列，可以按任意順序返回答案

?回溯法

一種通過探索所有可能的候選解來找出所有的解的算法。如果候選解被確認不是一個解（或者至少不是最后一個解），回溯算法會通過在上一步進行一些變化拋棄該解，即回溯并且再次嘗試。

方法一：回溯

有?n?個排列成一行的空格，從左往右依此填入題目給定的?n?個數，每個數只能使用一次。以想到一種窮舉的算法，即從左往右每一個位置都依此嘗試填入一個數，看能不能填完這?n?個空格，在程序中用「回溯法」來模擬這個過程。

定義遞歸函數?backtrack(first,output)，表示從左往右填到第?first?個位置，當前排列為?output。 那么整個遞歸函數分為兩個情況：

如果?first=n，說明已經填完了?n?個位置（注意下標從?0?開始），找到了一個可行的解將?output?放入答案數組中，遞歸結束

如果 first<n，要考慮這第 first 個位置要填哪個數。根據題目要求不能填已經填過的數，因此很容易想到的一個處理手段是定義一個標記數組 vis 來標記已經填過的數，那么在填第?first?個數的時候遍歷題目給定的?n?個數，如果這個數沒有被標記過，就嘗試填入，并將其標記，繼續嘗試填下一個位置，即調用函數?backtrack(first+1,output)。回溯的時候要撤銷這一個位置填的數以及標記，并繼續嘗試其他沒被標記過的數。

使用標記數組來處理填過的數是一個很直觀的思路，但是可不可以去掉這個標記數組呢？畢竟標記數組也增加了算法的空間復雜度。

答案是可以的，可以將題目給定的 n 個數的數組 nums 劃分成左右兩個部分，左邊的表示已經填過的數，右邊表示待填的數，在回溯的時候動態維護這個數組即可。

具體來說，假設已經填到第?first?個位置，那么?nums?數組中?[0,first?1]?是已填過的數的集合，[first,n?1]?是待填的數的集合，嘗試用?[first,n?1]?里的數去填第?first?個數，假設待填的數的下標為?i，么填完以后將第?i?個數和第?first?個數交換，即能使得在填第 first+1 個數的時候 nums 數組的 [0,first] 部分為已填過的數，[first+1,n?1] 為待填的數，回溯的時候交換回來即能完成撤銷操作。

舉個簡單的例子，假設有 [2,5,8,9,10] 這 5 個數要填入，已經填到第 3 個位置，已經填了 [8,9] 兩個數，那么這個數組目前為 [8,9?∣?2,5,10] 這樣的狀態，分隔符區分了左右兩個部分。假設這個位置要填 10 這個數，為了維護數組，我們將 2 和 10 交換，即能使得數組繼續保持分隔符左邊的數已經填過，右邊的待填 [8,9,10?∣?2,5] 。

輸入：nums = [1, 2, 3]
目標：生成所有可能的排列。

class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""def backtrack(first=0):  #定義回溯函數用于遞歸生成所有排列,first 代表當前正在填充的索引位置，默認從 0 開始,該函數的目標是通過交換 nums 中的元素，生成所有可能的排列if first==n:  #說明 nums 的排列已經完成res.append(nums[:])#nums 的拷貝（不能直接 append(nums)，否則后續的修改會影響結果）for i in range(first,n):#遍歷索引 first 到 n-1 之間的所有元素nums[first],nums[i]=nums[i],nums[first]#將 nums[i] 交換到 first 位置，使其成為當前排列的第 first 個數backtrack(first+1)#填充下一個位置的數nums[first],nums[i]=nums[i],nums[first]#nums是原地修改的，在回溯后需要撤銷之前的交換，恢復數組原狀，避免影響其他排列的生成n=len(nums)res=[]backtrack()return res

時間復雜度：O(n×n!)，其中?n?為序列的長度

空間復雜度：O(n)，其?n?為序列的長度。除答案數組以外，遞歸函數在遞歸過程中需要為每一層遞歸函數分配棧空間，

源自力扣官方題解
?