Problem statement:

Let, S = {S1 …. Sn} be a set of n positive integers, then we have to find a subset whose sum is equal to given positive integer d.It is always convenient to sort the set’s elements in ascending order. That is, S1 ≤ S2 ≤…. ≤ Sn

Algorithm:

Let, S is a set of elements and m is the expected sum of subsets. Then:

1. Start with an empty set.

2. Add to the subset, the next element from the list.

3. If the subset is having sum m then stop with that subset as solution.

4. If the subset is not feasible or if we have reached the end of the set then backtrack through the subset until we find the most suitable value.

5. If the subset is feasible then repeat step 2.

6. If we have visited all the elements without finding a suitable subset and if no backtracking is possible then stop without solution.

Example: Solve following problem and draw portion of state space tree M=30,W ={5, 10, 12, 13, 15, 18}

Solution:

The state space tree is shown as below in figure. {5, 10, 12, 13, 15, 18}