关于回溯算法的定义,百度百科上是这样描画的:回溯算法实践上一个相似枚举的搜索尝试进程,主要是在搜索尝试进程中寻觅成绩的解,当发现已不满足求解条件时,就“回溯”前往,尝试别的途径。回溯法是一种选优搜索法,按选优条件向前搜索,以到达目的。但当探求到某一步时,发现原先选择并不优或达不到目的,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个形状的点称为“回溯点”。许多复杂的,规模较大的成绩都可以运用回溯法,有“通用解题办法”的美称。
看明白没,回溯算法其实就是一个不断探求尝试的进程,探求成功了也就成功了,探求失败了就在退一步,继续尝试……,
组合总和
组合总和算是一道比较经典的回溯算法题,其中有一道题是这样的。
找出一切相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
阐明:
一切数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输入: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输入: [[1,2,6], [1,3,5], [2,3,4]]
这题说的很明白,就是从1-9中选出k个数字,他们的和等于n,并且这k个数字不能有重复的。所以第一次选择的时分可以从这9个数字中任选一个,沿着这个分支走下去,第二次选择的时分还可以从这9个数字中任选一个,但由于不能有重复的,所以要扫除第一次选择的,第二次选择的时分只能从剩下的8个数字中选一个……。这个选择的进程就比较阴暗了,我们可以把它看做一棵9叉树,除叶子结点外每个节点都有9个子节点,也就是下面这样
从9个数字中任选一个,就是沿着他的任一个分支不断走下去,其实就是DFS(假设不懂DFS的可以看下373,数据结构-6,树),二叉树的DFS代码是下面这样的
public static void treeDFS(TreeNode root) {
if (root == null)
return;
System.out.println(root.val);
treeDFS(root.left); treeDFS(root.right);}
这里可以仿照二叉树的DFS来写一下9叉树,9叉树的DFS就是经过递归遍历他的9个子节点,代码如下
public static void treeDFS(TreeNode root) {
//递归必需要有终止条件
if (root == null)
return;
System.out.println(root.val); //经过循环,辨别遍历9个子树
for (int i = 1; i <= 9; i++) {
//2,一些操作,可有可无,视状况而定
treeDFS("第i个子节点");
//3,一些操作,可有可无,视状况而定
}}
DFS其实就相当于遍历他的一切分支,就是列出他一切的能够结果,只需判别结果等于n就是我们要找的,那么这棵9叉树最多有多少层呢,由于有k个数字,所以最多只能有k层。来看下代码
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<>(), k, 1, n);
return res;
}private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {
//终止条件,假设满足这个条件,再往下找也没什么意义了
if (list.size() == k || n <= 0) {
//假设找到一组适宜的就把他参加到集合list中
if (list.size() == k && n == 0)
res.add(new ArrayList<>(list));
return;
}
//经过循环,辨别遍历9个子树
for (int i = start; i <= 9; i++) {
//选择以后值
list.add(i);
//递归
dfs(res, list, k, i + 1, n - i);
//撤销选择
list.remove(list.size() - 1);
}
}
代码相对来说还是比较复杂的,我们来剖析下(假设看懂了可以直接跳过)。
代码dfs中最末尾的中央是终止条件的判别,之前在426,什么是递归,经过这篇文章,让你彻底搞懂递归中讲过,递归必需要有终止条件。
(责任编辑:admin)