做凸透镜成像的网站,个人主页不会展示哪些内容,东营科技职业学院招生信息网官网,企业电子商城网站建设回溯方法的理论原理与定义
回溯算法是潜藏于递归过程之中一种操作#xff0c;与递归操作相辅相成#xff1b;初步理解#xff0c;有递归必有回溯#xff0c;使用回溯最好的方式是递归#xff0c;至于其他的方式有待探索。回溯是一种多重循环的变体#xff0c;其本质就是…回溯方法的理论原理与定义
回溯算法是潜藏于递归过程之中一种操作与递归操作相辅相成初步理解有递归必有回溯使用回溯最好的方式是递归至于其他的方式有待探索。回溯是一种多重循环的变体其本质就是对一个可选元素集合进行不断的循环遍历直到输出所有可行的结果回溯可用于解决组合问题、排列问题、棋盘问题、子集问题、切割问题回溯的过程可以可视化为多叉树每一种当前的元素挑选都将在多叉树上开辟一条新的分枝而提升回溯时间的效率的操作名为剪枝联合多叉树的可视化结果显然这个概念也不难理解了剪枝的本意在于“当前结果集的可选内容无法满足可行结果的继续计算因此我们提前停止避免额外的计算”要熟练回溯的模版 代码随想录 void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}第77题. 组合
思路使用回溯法进行多层遍历实现解题可使用剪枝加快不可满结果继续计算时就提前结束当前的分支的递归过程。
// 时间复杂度O((n1)n/2) O(n^2)
// 空间复杂度O(n^2)class Solution {public ListListInteger combine(int n, int k) {ListListInteger ans new ArrayList();ListInteger list new ArrayList();boolean[] visited new boolean[n];backtracking(0, n, k, -1, list, ans);return ans;}// 参数说明// count用来计数list中元素的个数// nk不解释// index用来剪枝颠倒组合的情况发生保证只有一个方向的组合// list存储每一次形成的可行组合ans全局结果集public void backtracking(int count, int n, int k, int index, ListInteger list, ListListInteger ans){// 停止条件if(count k){ans.add(new ArrayListInteger(list)); // 收集结果return;}// 剪枝用的用的是k-count还需要几个数与n-index-1还剩几个可选进行的比较用来剪枝if(k-count n-index-1)return;// 递归处理for(int i index1; in; i){count;list.add(i1);backtracking(count, n, k, i, list, ans);// 回溯count--;list.remove(list.size()-1);}return;
}}
