Write an algorithm of sum of subsets.

8.1kviews

written 8.4 years ago by

teamques10 ★ 68k

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)

ADD COMMENT EDIT