解釋
回溯法是一種優(yōu)先搜索法贝淤，按選優(yōu)條件向前搜索柒竞，以達(dá)到目標(biāo)，簡單來說就是一條路往前走播聪，能進(jìn)則進(jìn)，不能則退布隔，其實(shí)現(xiàn)核心是利用遞歸實(shí)現(xiàn)离陶。
步驟拆分
因?yàn)榫W(wǎng)上的的解釋的如出一轍，讓人看不懂衅檀，我按照自己的理解把回溯法拆分幾個(gè)要點(diǎn)招刨。
1、不斷向前搜索（遞歸）
2哀军、設(shè)立滿足回退條件
3沉眶、標(biāo)記已搜索節(jié)點(diǎn)
3、回退
下面用實(shí)例加備注詳解每個(gè)步驟：
求所有排列子集[1 2 3] --> [123 132 231 213 321 312]
func permute(nums []int) [][]int {
var res [][]int
if len(nums) == 0 {
return res
}
var tmp []int //結(jié)果子集
var visited = make([]bool, len(nums)) //標(biāo)記
backtracking(nums, &res, tmp, visited) //搜索方式
return res
}
func backtracking(nums []int, res *[][]int, tmp []int, visited []bool) {
if len(tmp) == len(nums) { //回退條件
var c = make([]int, len(tmp))
copy(c, tmp)
*res = append(*res, c)
return
}
// 回溯
for i := 0; i < len(nums); i++ {
if !visited[i] {
visited[i] = true //標(biāo)記搜索節(jié)點(diǎn)
tmp = append(tmp, nums[i]) //添加滿足條件解
backtracking(nums, res, tmp, visited) //向前搜索
tmp = tmp[:len(tmp)-1] //回退上一個(gè)節(jié)點(diǎn)
visited[i] = false
}
}
}
