代码随想录Day42

回溯算法理论基础：

回溯算法的本质是穷举，可以通过剪枝来优化回溯的效率。

回溯问题一般应用于：

组合问题、切割问题、子集问题、排列问题、棋盘问题

组合和排列的区别在于：

组合不强调元素顺序，排列强调元素的顺序。

回溯问题都可以抽象为树形结构，集合的大小和递归的深度构成树的宽度和深度。

回溯模板：

1.返回值和参数

2.终止条件

3.回溯遍历搜索的过程

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

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