title	tags	author	description
0046.Permutations	Medium, Backtracking	Kimi Tsai <kimi0230@gmail.com>

46. Permutations

題目

Given a collection of distinct integers, return all possible permutations(排列). Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

題目大意

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

解題思路

解決回朔問題可用一個決策樹的遍歷過程

路徑: 也就是已經做的選擇
選擇列表: 也就是當前可以做的選擇
結束條件: 也就是達到決策樹底層, 無法再做選擇的條件

result = []
def backtrack(路徑, 選擇列表):
	if 滿足結束條件:
		result.add(路徑)
		return
	
	for 選擇 in 選擇列表:
		做選擇
		backtrack(路徑, 選擇列表)
		撤銷選擇

                       選擇:[1,2,3]
                            []
          [1]/              |[2]            \[3]
        [2]/  \[3]      [1]/  \[3]       [1]/  \[2]
        |[3]   |[2]     |[3]   |[1]      |[2]    |[1]   
結果  [1,2,3]  [1,3,2] [2,1,3] [2,3,1]  [3,1,2]  [3,2,1]

求出一個數組的排列組合中的所有排列，用 DFS 深搜即可。這個問題可以看作有 ñ 個排列成一行的空格，我們需要從左往右依此填入題目給定的 ñ個數，每個數只能使用一次。那麼很直接的可以想到一種窮舉的算法，即從左往右每一個位置都依此嘗試填入一個數，看能不能填完這ñ 個空格，在程序中我們可以用「回溯法」來模擬這個過程回溯法：一種通過探索所有可能的候選解來找出所有的解的算法。如果候選解被確認不是一個解（或者至少不是最後一個解），回溯算法會通過在上一步進行一些變化拋棄該解，即回溯並且再次嘗試。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

來源

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0046.Permutations/Permutations.go

時間複雜 O(n)

package permutations

func Permute(nums []int) [][]int {
	numsLen := len(nums)
	if numsLen == 0 {
		return [][]int{}
	}
	used, path, res := make([]bool, numsLen), []int{}, [][]int{}
	dfs(nums, numsLen, 0, path, &used, &res)
	return res
}

/*
generatePermutation: (輸入數組, 數組長度, 遞迴到第幾層depth, path, 使用過的, 結果)
找最短路徑用**BFS**, 其他時用**DFS**用得多一些, 因為遞迴較好寫
假設有棵滿的二叉樹,節點數為 N. 對DFS來說空間複雜度就是遞迴, 最壞的情況就是樹的高度 O(log N)
BFS算法, Queue每次都會存二叉樹一層的節點, 最壞的情況下空間複雜度應該就是樹的最下層的數量, 也就是 N/2. 空間複雜度 O(N)
DFS（深度優先搜索）通常使用堆棧（Stack）來實現。在DFS中，您首先處理一個節點，然後將其子節點按某種順序推入堆棧中，接著繼續處理堆棧頂部的節點，直到堆棧為空。
*/
func generatePermutation(nums []int, numsLen int, depth int, path []int, used *[]bool, res *[][]int) {
	if depth == numsLen {
		temp := make([]int, len(path))
		copy(temp, path)
		*res = append(*res, temp)
		return
	}

	for i := 0; i < numsLen; i++ {
		if !(*used)[i] {
			// 沒使用過, 將其紀錄走過
			(*used)[i] = true
			path = append(path, nums[i])
			generatePermutation(nums, numsLen, depth+1, path, used, res)
			path = path[:len(path)-1]
			// 回朔
			(*used)[i] = false
		}
	}
}