回溯法求解的经典问题(2) 子集和数问题 o已知(Ww1w2,…,wn和M,均为正数。要求找出w的和数等 于M的所有子集 求的子集是(11,13,7)和(24013,24,7),M=31,则满足要 例如:若n=4,(w1,W,W3,W)=(1 子集和数问题解的一种表示方法 若用W;的下标表示解向量,这两个解向量为(1,2,4)和 3,4 子集和数问题的解可以表示为k-元组(X1x2,…,x),1kn 并且不同的解可以是大小不同白 的元组。 o显式约束条件是x∈为整数且1jn} o隐式约束条件是 1)没有两个x是相同的; 2)wx的和为M; 3)x<x+1,1i<n(避免产生同一个子集的重复情况)回溯法求解的经典问题（2） 子集和数问题 已知(w1 , w2 , …, wn )和M，均为正数。要求找出wi的和数等 于M的所有子集。 例如：若n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31，则满足要 求的子集是(11,13,7)和(24,7). 子集和数问题解的一种表示方法 若用Wi的下标表示解向量，这两个解向量为(1,2,4)和 (3,4)。 子集和数问题的解可以表示为k-元组(x1 , x2 , …, xk ), 1≤k≤n 并且不同的解可以是大小不同的元组。 显式约束条件是xi∈{j|j为整数且1≤j≤n}。 隐式约束条件是 ◼ 1)没有两个xi是相同的; ◼ 2)wxi的和为M; ◼ 3)xi＜xi＋1 ,1≤i＜n（避免产生同一个子集的重复情况）