子集和问题就是 给出一个数组arr和一个值sum 输出满足和为sum的arr的子集
子集和问题 从某种程度上来说 其实就是 01背包问题的 子问题 还是取一种情况 不取是另外一种情况 然后 用回溯法...要求找出wi的和数等于M的所有子集。
例如:若n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31,则满足要求的子集是(11,13,7)和(24,7)....分析
子集和数问题解的一种表示方法
解由n-元组(x1, x2, …, xn)表示;
显式约束条件xi∈{0,1} ,1≤i≤n,如果没有选择Wi,则xi=0;如果选择了Wi,则xi=1。...于是上面的解可以表示为(1,1,0,1)和(0,0,1,1);
隐式约束条件(xi× wi)的和数为M
解空间的大小为2n个元组
子集和数的递归回溯算法
//找W(1:n)中和数为M的所有子集。...end SUMOFSUB
例子
n=6, M=30,W(1:6)=(5,10,12,13,15,18)
(当前和,当前处理的子数,剩余子数的和)