Question

Use backtracking to find a subset, if it exists, of the set {27, 24, 19, 14, 11, 8} with sum

a) 20. b) 41. c) 60.

Short answer

1. There is not a subset with sum 20 exists.
2. The subset with sum 41 is {27,14}.
3. The subset with sum 60 is {27,19,14}.

Step-by-step solution

Find the subset of sum 20.

(a)

Here the given set is {27, 24, 19, 14, 11, 8}.

Let the subset be S.

27 ,24 is not subset s because it is greater than 20.

19 cannot be in subset S, because the given set does not contain \({\bf{20 - 19 = 1}}\).

14 cannot be in subset S, because the given set does not contain \({\bf{20 - 14 = 6}}\).

11 cannot be in subset S, because the given set does not contain \({\bf{20 - 11 = 9}}\). While it contains 8.

8 cannot be in S, because there is no other element in the set that could help to get sum 20.

Thus, there is no solution.

Determine the subset of sum 41.

(b)

Let the subset S.

Let add the first element 27 to S. \({\bf{S = }}\left\{ {{\bf{27}}} \right\}\).

24 cannot be in S, because \({\bf{27 + 24 = 51}}\), greater than 41.

19 cannot be in S, because \({\bf{27 + 19 = 46}}\), greater than 41.

Add 14 to S. the \({\bf{27 + 14 = 41}}\).

So, the subset is \({\bf{S = }}\left\{ {{\bf{27,14}}} \right\}\).

Thus, the subset {27,14} with sum 41.

Find the subset of sum 60.

(c)

Let the subset S.

Let add the first element 27 to S. \({\bf{S = }}\left\{ {{\bf{27}}} \right\}\).

24 can be in S, because \({\bf{27 + 24 = 51}}\), then \({\bf{S = }}\left\{ {{\bf{27,24}}} \right\}\). No other number can be added in this set.

19 can be in S, because \({\bf{27 + 19 = 46}}\), So set \({\bf{S = }}\left\{ {{\bf{27,19}}} \right\}\).

Add 14 to S. the \({\bf{46 + 14 = 60}}\).

So, the subset is \({\bf{S = }}\left\{ {{\bf{27,19,14}}} \right\}\).

Thus, the subset {27, 19 ,14} with sum 60.

Therefore, the results are

1. There is not a subset with sum 20 exists.
2. The subset with sum 41 is {27,14}.
3. The subset with sum 60 is {27,19,14}.