回溯 剪枝去重 全排列

回溯通常与递归,剪枝合并使用,本文示例深度剪枝全排列,与回溯标记去重。

算法模板

backtracking() {
    if (终止条件) {
        存放结果;
    }

    for (选择:选择列表(可以想成树中节点孩子的数量)) {
        递归,处理节点;
        backtracking();
        回溯,撤销处理结果
    }
}

分析

  • backtracking 其实就是向树的叶子节点方向遍历
  • for循环可以理解是横向遍历
  • backtracking 就是纵向遍历

backtracking就是一直往深处遍历,总会遇到叶子节点,遇到了叶子节点,就要返回。
backtracking的下面部分就是回溯的操作,撤销本次处理的结果

唯一全排列

给定一个没有重复 数字的序列,返回其所有可能的全排列

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

分析

  • 全排列广度遍历(同层执行完毕状态进入下一层)
  • 深度去重,每个起点为路径源点。对路径待考察数据进行比对 ,确保不会两次加入同一路径
func permute(nums []int) [][]int {

    rs :=[][]int{}
    var backTrace func(int,[]int)

    backTrace = func(idx int, path []int){
        if idx >= len(nums){
            return 
        }
        if len(path)==len(nums){
            cp := make([]int,len(nums))
            copy(cp,path)
            rs = append(rs,cp)
            return
        }
        for i:=0;i<len(nums);i++{
            if len(path)>0{
                b := false
                for j:=0;j<len(path);j++{
                    if path[j]==nums[i]{
                        b = true
                        break
                    }
                }
                if b {
                    continue
                }
            }
            path=append(path,nums[i])
            backTrace(i, path)
            path = path[:len(path)-1]
        }
    }

    backTrace(0,[]int{})
    return rs
}

有重全排列

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
  • 所有去重排列,首先必须保证源数据有序
  • 去重方式有递归树中的同层(广度)去重,与分支(深度)去重
  • 本例使用同层去重,给访问过的数据打标志,使用continue 跳过
import "sort"
func permuteUnique(nums []int) [][]int {
    rs := [][]int{}
    var backTrace func([]int,[]bool)
    backTrace = func(path []int, vis []bool){
        if len(path)==len(nums) {
            cp := make([]int, len(nums))
            copy(cp,path)
            rs = append(rs, cp)
            return
        }
        for i:=0;i<len(nums);i++{
            // 纵向vis[i]标识递进状态,横向vis[i-1]回溯同层数据比对
            if vis[i]  || (i>0 && nums[i-1]==nums[i] && !vis[i-1]){ 
                continue
            }
            vis[i]=true
            backTrace(append(path,nums[i]),vis)
            vis[i]=false
        }
    }
    sort.Ints(nums)
    backTrace([]int{}, make([]bool,len(nums)))
    return rs
}

栈容器双链表

以二叉树的前序遍历为例

  • 入栈与出栈顺序相反,根,左,右 入出栈序
  • 出入频繁交替,动态调整,终至栈空
 import "container/list"

func preorderTraversal(root *TreeNode) []int {
   if root == nil {
       return nil
   }
   rs :=[]int{}
   st := list.New()
   st.PushBack(root)

   for st.Len()>0 {
       top := st.Back().Value.(*TreeNode)
       st.Remove(st.Back())
       if top != nil {
           rs = append(rs,top.Val)
       }
       if top.Right != nil {
           st.PushBack(top.Right)
       }
       if top.Left != nil{
           st.PushBack(top.Left)
       }
   }
   return rs
}

小结

  • 递归在回溯期会隐式自动恢复上下文,最内层条件终止,并不意味程序停止运行,会层层回退恢复,直到最外层。
  • 就全排列而言,for循环体内的递归,是广度同层回溯,
  • 同层回溯,通常需要手动清理必要的状态
  • 使用排序与标记状态数组,辅助目标数据去重
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!
开发者 @ 社科大
文章
107
粉丝
12
喜欢
84
收藏
41
排名:101
访问:4.6 万
私信
所有博文