| 回溯算法：排列与组合详解 | 您所在的位置：网站首页 › 排列数算法属于那种类型算法 › 回溯算法：排列与组合详解 |
回溯算法：排列与组合详解
|
一起养成写作习惯！这是我参与「掘金日新计划 · 4 月更文挑战」的第一天，点击查看活动详情。 回溯算法，本质上是一种穷举算法，属于暴力搜索算法的一种。它虽然可以使用剪枝进行优化，仍不高效，但却实用。它往往能够解决可以抽象成树形结构的问题，亦可以认为是使用 K 层 for循环实现搜索的问题： 组合问题：按一定规则在 N 个数中找出 K 个数的集合 切割问题：一个字符串按一定规则切割成子串，求子串个数或符合条件的子集 子集问题：在N 个数的集合中，存在按一定规则分割出的符合某些条件的子集 排列问题：N 个数按一定规则全排列，求其排列结果 棋盘问题：N 皇后问题、数独问题、迷宫问题等等注：组合与全排列最大的不同就是，子集划分是否强调元素顺序，强调顺序的为全排列，即组合只往后看，排列前后都要看，可从下图清晰观察到两者的差别。 排列每层都是从 0 开始 排列需要 used 数组记录元素是否使用过，一个排列中元素只能使用一次在回溯算法中，我们需要清楚以下几种规则即可： 使用回溯算法前，可先将问题转化为树形结构 回溯算法解决问题都是在集合中递归子集，即常常以递归为基础实现的 回溯算法基本可以抽象成一颗 N 叉树形式的问题树，其宽度为集合大小，递归（纵向遍历）深度为树的深度 回溯算法常常使用 for 循环来遍历集合区间，即层次（横向）遍历问题树 回溯算法解决的问题结果常常在叶子结点之上 回溯算法需要考虑集合内元素是否可以重复选取，要求不同，方案不同 回溯算法常常使用布尔数组（used）来进行去重工作，必须先对目标集合（存在重复元素）进行排序才能去重 树层去重：子集内可重复，子集间不可重复 树枝去重：子集内不可重复，子集间可重复回溯算法剪枝优化常常从可获取的子集中剩余元素条件与要求元素条件相比较，不符合就剪枝 回溯算法如果在递归函数调用前，对全局变量有所调整，必须在递归函数后添加撤销语句 在了解到回溯算法的几项规则之后，再提供一套回溯算法的模板，如下： 确定回溯算法的返回值和相关参数 返回值一般为 void ，最终结果常常定义为全局参数 相关参数将会与回溯递归函数的相关参数一致，以递归要求为依据确定 确定回溯递归函数的终止条件 注意剪枝判断在递归终止判断之前 递归一定需要终止，即纵向遍历终止条件 终止就意味着满足了题目要求的条件存储结果，或者剪枝去除提高效率 确定单层遍历的过程 单层遍历即横向遍历，需要注意两个点，for 循环起始点及终止点，必须保证遍历完全 起始点与集合大小、是否可重复选取、是否需要去重、是否为排列问题、是否为组合问题等等有关 终止点与集合大小、剪枝条件等等伪代码模板如下： //全局变量 最终结果二维集：stack result; 符合条件结果：stack path; //函数体 void backtracking(参数){ if(剪枝条件){ 剪枝语句 } if(终止条件){ 存放结果; return; } for(选择符合条件的本层元素){ 处理结点; backtracking(参数); 撤销语句; } } 复制代码接下来将结合相关实例说明规则和模板的具体使用与注意点。 组合问题 题目详情LeetCode 题号：40. 组合总和 II 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意：解集不能包含重复的组合。 示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [[1,1,6],[1,2,5],[1,7],[2,6]] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 输出: [[1,2,2],[5]] 提示: 1 |
【本文地址】