有人说算法导论中没有回溯和分支定界这两种算法。我觉得这个算是导论中算法的应用吧，废话不多说，走起。
回溯算法之子集和数问题。
这个算法要解决的问题：假定有N个不同的正数(通常称为权)，要求找出这些数中所有使得某和数为M的组合。
这种问题的解的形式：(1)问题的解是大小固定的N元组，解向量中的元素的个数就是正数的个数，每个元素为X(i)，它的取值为0或者1，表示这个解是否包 含了相对应的正数W(i)。
(2)问题的解是大小不固定的K元组，这里不做讨论。
这样的整个的求解过程就构成了一棵树，对于i级上的一个结点，其左儿子是对应于X(i)=1产生的状态，右儿子是对应于X(i)=0产生的状态(父节点到儿子节点的边可以看成一种决策，这种决策就是选不选这个正数)。
但是为了防止这棵树长得很大，我们可以引入限界函数，可以提前预知这个结点不可能产生最后的解，这样我们就能提前的杀死这个结点，同时也能够提前的杀死这个结点的所有的子树，这样就大大的减少了树的节点数，加快了产生最终解的速度。
限界函数的产生：
(1)我们假设一个前提条件：这些正数是按照非降次序排列的。
(2)引入一个记号：B(X(1)，...，X(k))表示是否可以把第K个正数加入进来，所以它的取指为true或者false。
那么当我们考虑是否要把第K个正数加入到解向量中的时候，我们就能找到两个条件组成这个限界函数了：
(1)
这个公式的含义是：当你考虑是否要把第K个正数加入到解向量的时候，不管你要加进来或者是不打算把它加进来，前K个解向量的和(包括第K个，当然X(k)可能是0或者1)，加上后面所有的数的和一定要大于等于M，否则你把剩下的数都加了进来还比M小，这次的决策X(k)=0或者1肯定得不到满足条件的解向量。所以也就没有必要扩展这个结点的左儿子或者右儿子了。(说的明白点，如果X(k)=1不满足上面的式子，那就没有必要扩展第K-1个正数的左儿子了；右儿子同理；如果还不理解不要紧，看后面的例子)
(2)
这个公式的含义是，当你考虑是否要把第K个正数加入到解向量的时候，不管你要加进来或者是不打算把它加进来，提前往后看一步，判断如果把第K+1个正数算进来后的值大于M，就不把第K个正数加进来。也就是说不生成第K-1个节点的儿子。(说明白点，不管你的第K个结点是否加入到解向量中，如果X(k)=1不满足上面的式子，那就没有必要扩展第K-1个正数的左儿子了；右儿子同理；如果还不理解不要紧，看后面的例子)
注意：这个条件可能很难理解，首先这些数是非降序排列的，如果要考虑加入这个第K个数的话，分三种情况：
①加入进来刚好等于M，那么正好就得到了一个解向量。此时不要产生这个结点，因为提前向后看一步肯定会不满足(2)的，所以这种情况下树已经被界限函数杀死了，但是确实找到了正确的解向量，所以程序中的动作是输出这个解向量。树中的表现形式是，产生一个不同于普通结点的终结结点表示找到了一个正确的解向量。(后面的图中有区分，方块表示扩展了的结点，圆圈表示正确的解向量)
②加入进来的正数求和后小于M，往后看一步，看第K+1个节点，如果在加上第K+1个正数后的和大于M，则后面就不会再有满足条件的解向量了，因为这些正数是非降序排列的。后面的每个数和前面的这K个数的和一定都大于M；同时前面的K-1个数的和小于M。也就是说不会产生解向量，这这个第K个结点就不会加入到树中来，树在这里被界限函数杀死。
③加入进来的正数求和后大于M，因为这些正数是非降序排列的，显而易见不能产生解向量。
同时，如果决策是不加如这个第K个正数(产生右孩子)，如果前面这K个数的和(包括第K个的X(k)=0)加上第K+1个数的和大于M，也不会产生解向量，同样可以不用产生这个右孩子。
只有同时满足(1)(2)两个条件的时候，B(X(1)，...，X(k))=true，也就是说可以产生第K个正数的结点，否则就要在他的上级结点杀死。
注意：其实回溯算法很简单，但是重点和难点在于找到最后的界限函数，界限函数找的好就能提前杀死好多的节点，大大的提高算法的效率，如果界限函数找的不好就会是一个很烂的算法。
好了，界限函数也明确了，下面先看看伪代码：
1 procedure SUMOFSUB(s,k,r)2 //找W(1：n)中和数为M的所有子集。进入此过程时X(1),…,X(k-1)的值已确定。W(j)按非降次序排列。//
3 //下面的变量解释：s表示已经加进来的这个序列的和；r表示还没有加入进来的所有的数的和；k表示级数//4 globalinteger M,n;5 global real W(1:n);6 global boolean X(1:n);7 real r, s;8 integer k,j;9 //生成左儿子//10 X(k)←111 if s+W(k)=M then12 print(X(j),j←1to k)13 else
14 //这里指判断了界限函数的一个条件：我们假设所有的数的和大于等于M，否则没意义了，将一定无解；还假设第一个数小于等于M//15 if s+W(k)+W(k+1) ≤ M then//B(k)=true//16 call SUMOFSUB(S+W(k),k+1,r-W(k))17 endif18 endif19 //生成右儿子和计算Bk的值//20 if s+r-W(k) ≥ M and s+W(k+1) ≤ M//B(k)=true//21 then X(k)←0
22 call SUMOFSUB(s,k+1,r-W(k))23 endif24 end SUMOFSUB
注解：为什么第二个if中只判断了一个条件?因为我们一开始就假设所有的数的和大于等于M，所以在生成左孩子的时候，这个条件一定满足，因为我们的做法是把这个数加进来。只要他的父结点满足条件，它就满足条件(父结点如果是根，我们有假设；父结点如果是爷爷结点的右孩子，那么父结点判断界限函数了；父结点是爷爷结点的左孩子，那么往上递推)。
可能到这里还有好多的不明白，那么我们来实际的跑一次：
设n=4个正数的集合，W={11,13,24,7}，和M=31。求W的所有元素之和为M的子集。
解：
注意：(1)最后的解不是一个结点，而是在上一级就截断了，用小圆圈表示这个解。还有A结点的打印输出不是N元组。
(2)一定要先对所有的正数排序。
(3)构建上面的树的时候，产生一个结点，如果要接着构建其左孩子，那么让他入栈，等到轮到他的时候再出栈构建其右孩子。
--------------------------------------------------------------------------------------------------
好了，铺垫了那么久，终于该轮到代码上场了，看看具体的实现(其实最终要的还是界限函数的选取，不要本末倒置)：
1 #include
2 #define M 31
3 #define N 5
4
5 int w[N] = {0,11,13,24,7};6 int x[N] = {0};7 int flag = 0;8
9 //回溯算法实现
10 void sumOfSub(int s, int k, intr);11 //首先对这些正数排序
12 void InsertionSort(int a[], int low, inthigh);13 //每产生一个解向量就打印出来，同时清零。准备下一个解向量
14 voidprint();15
16 intmain()17 {18 int sum = 0;19 //先判断所有数的和是否小于M，如果小于M则不会有解向量
20 for(int i=1; i
24
25 if(sum
31 //如果要用回溯算法，首先对数据排序。因为数据的规模不大，用InsertionSort搞定
32 InsertionSort(w, 1, N-1);33
34 if(w[0] >M)35 {36 printf("没有解向量满足条件\n");37 return 0;38 }//if39
40 //回溯算法的准备工作完毕，下面开始调用
41 sumOfSub(0,1,sum);42
43 //通过flag的值判断print()函数有没有被调用过，从而确定是否存在解向量
44 if(!flag)45 {46 printf("不存在满足条件的序列\n");47 }48
49 return 0;50 }51 void sumOfSub(int s, int k, intr)52 {53 //生成左子树
54 x[k] = 1;55 if(s + w[k] ==M)56 {57 print();58 }//if
59 else
60 {61 if(k < N - 1 && s + w[k] + w[k+1] <=M)62 {63 sumOfSub(s+w[k], k + 1, r -w[k]);64 }//if
65
66 }//else67
68 //生成右子树
69 x[k] = 0;70 if(k < N - 1 && s + r - w[k] >= M && s + w[k+1] <=M)71 {72 sumOfSub(s, k + 1, r -w[k]);73 }//if
74
75 }76
77 voidprint()78 {79 for(int i=1; i
87 void InsertionSort(int a[], int low, inthigh)88 {89 int unsort = low + 1;90 intj;91 for(;unsort <= high; ++unsort)92 {93 int temp =a[unsort];94 j = unsort - 1;95 while(j >= 0 && temp
100
101 a[j+1] =temp;102 }//for
103 }
测试：
(1)程序数据：{5,10,12,13,15,18}程序结果：
(2)程序数据：{11,13,24,7}
程序结果：
未完待续：
回溯算法的子集和数问题到此告一段落，有时间再追加时间复杂度。
如果觉得《java子集和数问题回溯法算法_子集和数问题_回溯》对你有帮助，请点赞、收藏，并留下你的观点哦！
