营销型网站内容,湖南省建设厅政务中心网站,商务网站的建设与维护,泰安市人才信息网从这道题开始#xff0c;我们正式进入回溯算法的学习。之前在二叉树中只是接触到了一丢丢#xff0c;而这里我们将使用回溯算法解决很多经典问题。
那么这道题是如何使用回溯算法的呢#xff1f;在讲回溯之前#xff0c;先说明一下此题是如何递归的。毕竟回溯递归不分家我们正式进入回溯算法的学习。之前在二叉树中只是接触到了一丢丢而这里我们将使用回溯算法解决很多经典问题。
那么这道题是如何使用回溯算法的呢在讲回溯之前先说明一下此题是如何递归的。毕竟回溯递归不分家必须先有递归才会有回溯。而这里的递归就是在题目所给集合的子集中使用for循环选择数字。考虑组合的无序性(1,2和2,1是相同的组合)那么在对递归得到的子集进行遍历时需要用变量控制for循环的起始位置。另外如果题目说明不能取重复数字那么在对该控制变量赋值时需要注意。举个例子最开始的集合有1,2,3,4那么我们第一次一定是从这个集合中选一个数。为了保证之后不重复选择1我们下一步一定是从2,3,4这个集合中选一个数以此类推。我们可以发现递归得到的子集范围在不断缩小。接下来讲一下回溯我们需要写一个for循环将递归函数包起来这个for循环的作用是遍历当前集合的所有数假设在第一个集合中我们已经选了1这个数然后递归选择第二个数那么在选择第二个数的递归函数结束之后我们可以将1弹出存储组合的数组并通过for循环选择第一个集合中的第二个数这样就得到了其他组合情况。这道题大家可以当做模版题记下来之后的回溯算法的代码风格都与这道题大差不差。可以结合我下面的代码及注释理解这道题。
代码及注释如下
class Solution {
private:vectorvectorint result; // 存放符合条件结果的集合vectorint path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n; i) {path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};
