這一篇主要講一講回溯，除了N皇后問題是困難題，不過N皇后知道了咋做也不難。回溯整體上還是好做的，直到套路容易做出來，題目容易理解。

回溯

[1]全排列

問：給定一個不含重復數字的數組?nums?，返回其?所有可能的全排列?。你可以?按任意順序?返回答案。

切片是引用，如果使用result = append(reslut,result1)，result1也是切片，那么result保存的都是指向同一個切片，不過會開辟空間。

func permute(nums []int) [][]int {result := [][]int{}var process func(index int)process = func(index int) {if index == len(nums) {tmp := make([]int, len(nums))copy(tmp, nums)result = append(result, tmp)return}for i := index; i < len(nums); i++ {nums[index], nums[i] = nums[i], nums[index]process(index + 1)nums[index], nums[i] = nums[i], nums[index]}}process(0)return result
}

[2]子集

問：給你一個整數數組?nums?，數組中的元素?互不相同?。返回該數組所有可能的子集（冪集）。

解集?不能?包含重復的子集。你可以按?任意順序?返回解集。

考慮選不選問題，而不需要遍歷整個數組，只需要考慮當前元素。

func subsets(nums []int) [][]int {result := [][]int{}result1 := []int{}var process func(index int)process = func(index int) {if index==len(nums){tmp := make([]int,len(result1))copy(tmp,result1)result = append(result, tmp)return }process(index+1)result1 = append(result1, nums[index])process(index+1)result1 = result1[:len(result1)-1]}process(0)return result
}

[3]電話號碼的字母組合

問：給定一個僅包含數字?2-9?的字符串，返回所有它能表示的字母組合。答案可以按?任意順序?返回。

用哈希表存儲數字對應的字母就好。

func letterCombinations(digits string) []string {if len(digits)==0{return []string{}}result := []string{}m := map[int]string{2: "abc",3: "def",4: "ghi",5: "jkl",6: "mno",7: "pqrs",8: "tuv",9: "wxyz"}var process func(index int)result1 := ""process = func(index int) {if index==len(digits){result = append(result, result1)return}var in intin = int(digits[index] - '0')for _,e := range m[in]{result1 = result1 + string(e)process(index+1)result1 = result1[:len(result1)-1]}}process(0)return result
}

[4]括號生成

問：數字?n?代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且?有效的?括號組合。

主要是考慮當前情況是只能選擇(還是能夠有兩種選擇。

func generateParenthesis(n int) []string {result := []string{}str :=  ""var process func(index int,num int,right int)process = func(index int,left int,right int) {if index == 2*n{result = append(result, str)return}if left >0{str += "("process(index+1,left-1,right+1)str = str[:len(str)-1]}if right>0{str += ")"process(index+1,left,right-1)str = str[:len(str)-1]}}process(0,n,0)return result
}

[5]組合總和

問：給你一個?無重復元素?的整數數組?candidates?和一個目標整數?target?，找出?candidates?中可以使數字和為目標數?target?的 所有?不同組合?，并以列表形式返回。你可以按?任意順序?返回這些組合。

func combinationSum(candidates []int, target int) [][]int {var process func(index int)total := 0result := [][]int{}result1 := []int{}process = func(index int) {if total == target{tmp := make([]int,len(result1))copy(tmp,result1)result = append(result, tmp)return}if total > target{return}for i:=index;i<len(candidates);i++{if candidates[i]==0{continue}total += candidates[i]result1 = append(result1, candidates[i])process(i)result1 = result1[:len(result1)-1]total -= candidates[i]}}process(0)return result
}

[6]單詞搜索

問：給定一個?m x n?二維字符網格?board?和一個字符串單詞?word?。如果?word?存在于網格中，返回?true?；否則，返回?false?。

這個回溯需要依賴外層雙循環，因為每個process只會判斷當前位置是否能夠滿足。注意的是需要臨時修改用過的格子的值，避免重復使用。

func exist(board [][]byte, word string) bool {length := len(board)high := len(board[0])flag := falsevar process func(x, y int, index int)process = func(x, y int, index int) {if index == len(word) {flag = truereturn}if x < 0 || y < 0 || x >= length || y >= high {return}if board[x][y] == word[index] {tmp := board[x][y]board[x][y] = '0'process(x+1, y, index+1)process(x, y+1, index+1)process(x, y-1, index+1)process(x-1, y, index+1)board[x][y] = tmp}}for i := 0; i < length; i++ {for j := 0; j < high; j++ {process(i, j, 0)}}return flag
}

[7]分割回文串

問：給你一個字符串?s，請你將?s?分割成一些?子串，使每個子串都是?回文串?。返回?s?所有可能的分割方案。

寫這道題的時候依然犯了一個致命的錯誤，切片是索引，如果將result1保存到result中會導致出乎意料的結果！不過這里將每次傳遞空字符串其實有點傻，可以改進。

func partition(s string) [][]string {result := [][]string{}result1 := []string{}var isTure func(str string) boolisTure = func(str string) bool {left := 0right := len(str)-1for left < right {if str[left]!=str[right]{return false}left++right--}return true}var process func(index int,str string)process = func(index int,str string) {if index==len(s){temp := make([]string, len(result1))copy(temp, result1)result = append(result, temp)return}for i:=index;i<len(s);i++{str += string(s[i])if isTure(str){result1 = append(result1, str)process(i+1,"")result1 = result1[:len(result1)-1]}}return}process(0,"")return result
}

[8]N皇后

問：按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n?皇后問題?研究的是如何將?n?個皇后放置在?n×n?的棋盤上，并且使皇后彼此之間不能相互攻擊。給你一個整數?n?，返回所有不同的?n?皇后問題?的解決方案。