Problem statement:
Let, $S = {S_1 …. S-n}$ 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, $S_1 ≤ S_2 ≤…. ≤ S_n$
Algorithm:
Let, S is a set of elements and m is the expected sum of subsets. Then:
- Start with an empty set.
- Add to the subset, the next element from the list.
- If the subset is having sum m then stop with that subset as solution.
- 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.
- If the subset is feasible then repeat step 2.
- 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 = 35, W = (5, 7, 10, 12, 15, 18, 20)
Solution:
Initially subset = {} |
Sum = 0 |
Description |
5 |
5 |
Then add next element. |
5, 7 |
12,i.e. 12 < 35 |
Add next element. |
5, 7, 10 |
22,i.e. 22 < 35 |
Add next element. |
5, 7, 10, 12 |
34,i.e. 34 < 35 |
Add next element. |
5, 7, 10, 12, 15 |
49 |
Sum exceeds M = 35. Hence backtrack. |
5, 7, 10, 12, 18 |
52 |
Sum exceeds M = 35. Hence backtrack. |
5, 7, 10, 12, 20 |
54 |
Sum exceeds M = 35. Hence backtrack. |
5, 12, 15 |
32 |
Add next element. |
5, 12, 15, 18 |
50 |
Not feasible. Therefore backtrack |
5, 12, 18 |
35 |
Solution obtained as M = 35 |
The state space tree is shown as below in figure 8. (5, 7, 10, 12, 15, 18, 20)