这一篇主要讲一讲回溯，除了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 int
in = 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 := 0
result := [][]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 := false
var process func(x, y int, index int)
process = func(x, y int, index int) {
if index == len(word) {
flag = true
return
}
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) bool
isTure = func(str string) bool {
left := 0
right := len(str)-1
for 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 皇后问题 的解决方案。
