•
例 2 ：子集和数问题
•
已知 n+1 个正数 试求出 的和是 M 的
所有子集。
•
例 n=4 M=31 ，则满足要求的
子集合为 {11,13,7},{24,7}
•
（ 1 ）用不定长的元组表示，则解为 k 元组
•
为避免产生同一个子集的重复情况，可附加
•
（ 2 ）用定长元组表示，则每个结点表示为
•
则子集合 {11,13,7} 可表示为 (1,1,0,1)
•
{7,24} 可表示为 (0,0,1,1)
4/21
1
,
n
w w m
i
w
1 2 3 4
{ , } {11,13, 24,7}w w w w
1
{ , },
k
x x k n
1i i
x x
1
( , )
n
x x
第八章 回溯法
§1 、 一般方法
