回溯

Mike大约 2 分钟

回溯

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法并不是什么⾼效的算法，如果想让回溯法⾼效⼀些，可以加⼀些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法解决的问题可以概括如下：

组合问题：N个数⾥⾯按⼀定规则找出k个数的集合
切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式
⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集
排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式
棋盘问题：N皇后，解数独等等

回溯法解决的问题都可以抽象为树形结构。

回溯算法模板框架如下：

void backtracking(参数) {
    if (终⽌条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中孩⼦节点的数量就是集合的⼤⼩）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果;
    }
}

习题

回溯

# 回溯

# 习题

# 组合

# 分割

# 子集

# 排列

# 棋盘问题

# 其他

# 总结

回溯

习题

组合

分割

子集

排列

棋盘问题

其他

总结