Sum of Subsets

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_i = 1 and the right to x_i = 0.

A simple choice for bounding function is:

B_k(X₁,..,X_k) = true iff  ∑^k_i=1 W_iX_i + ∑^k_i=k+1 W<sub>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</sub>
 B_k(X₁,..,X_k) = true iff  ∑^k_i=1 W_iX_i + ∑^k_i=k+1 W_{i ≥ m and}
∑^k_i=1 W_iX_i + ∑^k_i=k+1 W_{i > m}