最优搜索-回溯算法

解释

回溯法是一种优先搜索法，按选优条件向前搜索，以达到目标，简单来说就是一条路往前走，能进则进，不能则退，其实现核心是利用递归实现。

步骤拆分

因为网上的的解释的如出一辙，让人看不懂，我按照自己的理解把回溯法拆分几个要点。
1、不断向前搜索（递归）
2、设立满足回退条件
3、标记已搜索节点
3、回退
下面用实例加备注详解每个步骤：
求所有排列子集[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                          //结果子集
    var visited = make([]bool, len(nums))  //标记
    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                     //标记搜索节点
            tmp = append(tmp, nums[i])            //添加满足条件解
            backtracking(nums, res, tmp, visited) //向前搜索
            tmp = tmp[:len(tmp)-1]                //回退上一个节点
            visited[i] = false
        }
    }
}