[[435870]]

給定一個(gè) 沒有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。

示例:

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

本題是回溯算法的經(jīng)典應(yīng)用場景

1. 算法策略

回溯算法是一種搜索法，試探法，它會(huì)在每一步做出選擇，一旦發(fā)現(xiàn)這個(gè)選擇無法得到期望結(jié)果，就回溯回去，重新做出選擇。深度優(yōu)先搜索利用的就是回溯算法思想。

2. 適用場景

回溯算法很簡單，它就是不斷的嘗試，直到拿到解。它的這種算法思想，使它通常用于解決廣度的搜索問題，即從一組可能的解中，選擇一個(gè)滿足要求的解。

3. 代碼實(shí)現(xiàn)

我們可以寫一下，數(shù)組 [1, 2, 3] 的全排列有：

先寫以 1 開頭的全排列，它們是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列;

再寫以 2 開頭的全排列，它們是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列;

最后寫以 3 開頭的全排列，它們是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

即回溯的處理思想，有點(diǎn)類似枚舉搜索。我們枚舉所有的解，找到滿足期望的解。為了有規(guī)律地枚舉所有可能的解，避免遺漏和重復(fù)，我們把問題求解的過程分為多個(gè)階段。每個(gè)階段，我們都會(huì)面對(duì)一個(gè)岔路口，我們先隨意選一條路走，當(dāng)發(fā)現(xiàn)這條路走不通的時(shí)候(不符合期望的解)，就回退到上一個(gè)岔路口，另選一種走法繼續(xù)走。

這顯然是一個(gè) 遞歸 結(jié)構(gòu);

• 遞歸的終止條件是：一個(gè)排列中的數(shù)字已經(jīng)選夠了 ，因此我們需要一個(gè)變量來表示當(dāng)前程序遞歸到第幾層，我們把這個(gè)變量叫做 depth ，或者命名為 index ，表示當(dāng)前要確定的是某個(gè)全排列中下標(biāo)為 index 的那個(gè)數(shù)是多少;
• used(object)：用于把表示一個(gè)數(shù)是否被選中，如果這個(gè)數(shù)字(num)被選擇這設(shè)置為 used[num] = true ，這樣在考慮下一個(gè)位置的時(shí)候，就能夠以 O(1)的時(shí)間復(fù)雜度判斷這個(gè)數(shù)是否被選擇過，這是一種「以空間換時(shí)間」的思想。

let permute = function(nums) { 
    // 使用一個(gè)數(shù)組保存所有可能的全排列 
    let res = [] 
    if (nums.length === 0) { 
        return res 
    } 
    let used = {}, path = [] 
    dfs(nums, nums.length, 0, path, used, res) 
    return res 
} 
let dfs = function(nums, len, depth, path, used, res) { 
    // 所有數(shù)都填完了 
    if (depth === len) { 
        res.push([...path]) 
        return 
    } 
    for (let i = 0; i < len; i++) { 
        if (!used[i]) { 
            // 動(dòng)態(tài)維護(hù)數(shù)組 
            path.push(nums[i]) 
            used[i] = true 
            // 繼續(xù)遞歸填下一個(gè)數(shù) 
            dfs(nums, len, depth + 1, path, used, res) 
            // 撤銷操作 
            used[i] = false 
            path.pop() 
        } 
       
    } 
} 

4. 復(fù)雜度分析

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

這是一個(gè)排列組合，每層的排列組合數(shù)為：Amn=n!/(n?m)! ，故而所有的排列有 ：

A1n + A2n + … + An-1n = n!/(n?1)! + n!/(n?2)! + … + n! = n! * (1/(n?1)! + 1/(n?2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2n-1) < 2 * n!

并且每個(gè)內(nèi)部結(jié)點(diǎn)循環(huán) n 次，故非葉子結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n?n!)

• 空間復(fù)雜度：O(n) 

leetcode：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-wen-ti-by-user7746o/