回溯剪枝去重 中文全排列

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

算法模板

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
}

中文字符全排列

不重复中文字符全排列，如”低中高”处理
用for...range 结构及 rune 类型处理中文组合

func permutation(S string) []string {
    src, rs := []rune(S), []string{}
    var backtrace func([]rune, []bool)
    backtrace = func(path []rune, vis []bool) {
        if len(path) == len(src) {
            rs = append(rs, string(path))
            return
        }
        for i, v := range src {
            if !vis[i] {
                vis[i] = true
                backtrace(append(path, v), vis)
                vis[i] = false
            }
        }
    }
    backtrace([]rune{}, make([]bool, len(src)))
    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 协议》，转载必须注明作者和本文链接