回溯法理论基础：

回溯法：

回溯搜索法，用于搜索，实际上是递归函数

效率：

是穷举，暴力搜索，效率不高。剪枝可以更高效。

应用场景：

组合问题：N个数里面按一定规则找出k个数的集合

切割问题：一个字符串按一定规则有几种切割方式

子集问题：一个N个数的集合里有多少符合条件的子集

排列问题：N个数按一定规则全排列，有几种排列方式

棋盘问题：N皇后，解数独等等

如何理解：

将问题抽象成树形结构，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。终止条件限制其为高度有限的N叉树。

回溯法模板：

void backtracking(参数) {

    if (终止条件) {

        存放结果;

        return;

    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {

        处理节点;

        backtracking(路径，选择列表); // 递归

        回溯，撤销处理结果

    }

}

77. 组合

思路：

按照模板，确定参数，终止条件和单层逻辑

确定参数：n,k

终止条件：一维数组的size==k，将一维数组放进二维数组

单层逻辑：for循环确认第一个元素，不知道应该用什么方式回溯

看视频后：

确认参数：

全局变量：一维数组，二维数组

参数：n,k,startIndex

终止条件：一维数组的size==k，将一维数组放进二维数组

单层逻辑：

for(int i=startIndex;i<=n;i++)

        {

            vec.push_back(i);

            backtracking(n,k,i+1);

            vec.pop_back();

        }

剪枝：

对单层逻辑中i的范围进行缩小，i<=n-(k-vec.size())+1

vec.size()为已有元素

k-vec.size()为还需要多少元素

n-(k-vec.size())+1为至多需要多少元素

剪枝最好是画出树图找到能剪枝的部分