每日算法：全排列問題
給定一個 沒有重復(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. 算法策略
回溯算法是一種搜索法，試探法，它會在每一步做出選擇，一旦發(fā)現(xiàn)這個選擇無法得到期望結(jié)果，就回溯回去，重新做出選擇。深度優(yōu)先搜索利用的就是回溯算法思想。
2. 適用場景
回溯算法很簡單，它就是不斷的嘗試，直到拿到解。它的這種算法思想，使它通常用于解決廣度的搜索問題，即從一組可能的解中，選擇一個滿足要求的解。
3. 代碼實現(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] 的全排列。
即回溯的處理思想，有點類似枚舉搜索。我們枚舉所有的解，找到滿足期望的解。為了有規(guī)律地枚舉所有可能的解，避免遺漏和重復(fù)，我們把問題求解的過程分為多個階段。每個階段，我們都會面對一個岔路口，我們先隨意選一條路走，當發(fā)現(xiàn)這條路走不通的時候(不符合期望的解)，就回退到上一個岔路口，另選一種走法繼續(xù)走。
這顯然是一個 遞歸 結(jié)構(gòu);
- 遞歸的終止條件是：一個排列中的數(shù)字已經(jīng)選夠了 ，因此我們需要一個變量來表示當前程序遞歸到第幾層，我們把這個變量叫做 depth ，或者命名為 index ，表示當前要確定的是某個全排列中下標為 index 的那個數(shù)是多少;
- used(object)：用于把表示一個數(shù)是否被選中，如果這個數(shù)字(num)被選擇這設(shè)置為 used[num] = true ，這樣在考慮下一個位置的時候，就能夠以 O(1)的時間復(fù)雜度判斷這個數(shù)是否被選擇過，這是一種「以空間換時間」的思想。
- let permute = function(nums) {
- // 使用一個數(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]) {
- // 動態(tài)維護數(shù)組
- path.push(nums[i])
- used[i] = true
- // 繼續(xù)遞歸填下一個數(shù)
- dfs(nums, len, depth + 1, path, used, res)
- // 撤銷操作
- used[i] = false
- path.pop()
- }
- }
- }
4. 復(fù)雜度分析
時間復(fù)雜度：O(n?n!)，其中 n 為序列的長度
這是一個排列組合，每層的排列組合數(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!
并且每個內(nèi)部結(jié)點循環(huán) n 次，故非葉子結(jié)點的時間復(fù)雜度為 O(n?n!)
- 空間復(fù)雜度：O(n)
leetcode：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-wen-ti-by-user7746o/
