数字拆分问题算法回溯_什么叫回溯算法，一看就会，一写就废

原标题：什么叫回溯算法，一看就会，一写就废

什么叫回溯算法

对于回溯算法的定义，百度百科上是这样描述的：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

看明白没，回溯算法其实就是一个不断探索尝试的过程，探索成功了也就成功了，探索失败了就在退一步，继续尝试……，

组合总和

组合总和算是一道比较经典的回溯算法题，其中有一道题是这样的。

找出所有相加之和为 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代码是下面这样的

1publicstaticvoidtreeDFS( TreeNode root){

2if(root == null)

3return;

4System. out.println(root.val);

5treeDFS(root.left);

6treeDFS(root.right);

7}

这里可以仿照二叉树的DFS来写一下9叉树，9叉树的DFS就是通过递归遍历他的9个子节点，代码如下

1publicstaticvoidtreeDFS( TreeNode root){

2//递归必须要有终止条件

3if(root == null)

4return;

5System. out.println(root.val);

6

7//通过循环，分别遍历9个子树

8for( inti = 1; i <= 9; i++) {

9//2，一些操作，可有可无，视情况而定

10

11treeDFS( "第i个子节点");

12

13//3，一些操作，可有可无，视情况而定

14}

15}

DFS其实就相当于遍历他的所有分支，就是列出他所有的可能结果，只要判断结果等于n就是我们要找的，那么这棵9叉树最多有多少层呢，因为有k个数字，所以最多只能有k层。来看下代码

1publicList> combinationSum3( intk, intn) {

2List> res = newArrayList<>;

3dfs(res, newArrayList<>, k, 1, n);

4returnres;

5}

6

7privatevoiddfs(List> res, List list, intk, intstart, intn){

8//终止条件，如果满足这个条件，再往下找也没什么意义了

9if( list.size == k || n <= 0) {