Suppose we are given n distinct numbers (usually called weights) and we desire to find all combinations of these numbers whose sums are m.This is called sum of subsets problem.We consider a backtracking solution using fixed tuple size strategy.

The children of any node in fig 6.4 are easily generated.For a node at level 1 the left child corresponds to x

A simple choice for bounding function is:

B

∑

The children of any node in fig 6.4 are easily generated.For a node at level 1 the left child corresponds to x

_{i}= 1 and the right to x_{i}= 0.A simple choice for bounding function is:

B

_{k}(X_{1},..,X_{k}) = true iff ∑^{k}_{i=1}W_{i}X_{i}+ ∑^{k}_{i=k+1}W_{i ≥ m}_{Assuming }_{Wi's in nondecreasing order, (}_{X1,..,Xk) cannot lead to an answer node if }_{∑ki=1 WiXi + ∑ki=k+1 Wi > m}_{So, the bounding function is}_{ }B_{k}(X_{1},..,X_{k}) = true iff ∑^{k}_{i=1}W_{i}X_{i}+ ∑^{k}_{i=k+1}W_{i ≥ m and }∑

^{k}_{i=1}W_{i}X_{i}+ ∑^{k}_{i=k+1}W_{i > m}_{ }