代码随想录算法训练营第二十四天|回溯算法理论、77组合

回溯算法模板

void backtracking(参数) {

    if (终止条件) {

        存放结果;

        return;

    }

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

        处理节点;

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

        回溯，撤销处理结果

    }

}

回溯和递归是相辅相成的

77. 组合  

递归函数的返回值以及参数：

在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合

参数：n和k、startIndex防止出现重复的组合

回溯函数终止条件：

终止条件代码：

if(path.size()==k){result.push_back(path);return;}

单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历

publicvoidbacktracking(intn,intk,intstartIndex){if(path.size()==k){result.add(newArrayList<>(path));return;}for(inti=startIndex;i<=n;i++){path.add(i);backtracking(n,k,i+1);path.removeLast();}}