Given a set of N coins C
=

{
c
1
,
c
2
,
c
3
,

.
.
.
,
cN
}
and a monetary value M

0
,
find the smallest subset of C that can pay value K
(
without change
)
.

Note that in this problem, C can have duplicates, and a coin can be used only once.

Examples. C
=

{
1
,

1
,

4
,

2
0
,

2
0
,

2
1
,

2
5
,

4
0
}

M
=

4
5
Answer
=

{
2
0
,

2
5
}
M
=

1
3
2
Answer
=

{
1
,

1
,

4
,

2
0
,

2
0
,

2
1
,

2
5
,

4
0
}
M
=

3
Answer
=
No subset meets the requirements

Design a backtracking algorithm to solve this problem. Follow the steps below:

A
.
Draw a tree showing how a brute
-
force enumeration algorithm enumerates the solutions for the following instance: C
=

{
2
,

2
,

4
}
M
=

4
.

Clearly show on the tree what each node and edge represents and which solutions are feasible and which are not.

B
.
Suggest a backtracking strategy to improve the running time of the brute
-
force algorithm.

C
.
Provide an example of values for C
{
at least
4
}
and M that will lead to:

1
.
No pruning in the tree.

2
.
Maximum pruning in the tree.

Question

Given a set of N coins C 
=
 
{
c
1
,
 ﻿c
2
,
 ﻿c
3
,
 
.
.
.
,
 ﻿cN
}
 ﻿and a monetary value M 
>
 
0
,
 ﻿find the smallest subset of C that can pay value K 
(
without change
)
.
﻿
Note that in this problem, C can have duplicates, and a coin can be used only once.
﻿
Examples. C 
=
 
{
1
,
 
1
,
 
4
,
 
2
0
,
 
2
0
,
 
2
1
,
 
2
5
,
 
4
0
}
 ﻿
﻿
﻿ M 
=
 
4
5
 ﻿ Answer 
=
 
{
2
0
,
 
2
5
}
﻿M 
=
 
1
3
2
 ﻿Answer 
=
 
{
1
,
 
1
,
 
4
,
 
2
0
,
 
2
0
,
 
2
1
,
 
2
5
,
 
4
0
}
﻿ M 
=
 
3
 ﻿ Answer 
=
 ﻿No subset meets the requirements
﻿
Design a backtracking algorithm to solve this problem. Follow the steps below:
﻿
A
.
 ﻿Draw a tree showing how a brute
-
force enumeration algorithm enumerates the solutions for the following instance: C 
=
 
{
2
,
 
2
,
 
4
}
 ﻿M 
=
 
4
.
﻿
Clearly show on the tree what each node and edge represents and which solutions are feasible and which are not.
﻿
B
.
 ﻿Suggest a backtracking strategy to improve the running time of the brute
-
force algorithm.
﻿
C
.
 ﻿Provide an example of values for C 
{
at least 
4
}
 ﻿and M that will lead to:
﻿
﻿ 
1
.
 ﻿No pruning in the tree.
﻿
﻿ 
2
.
 ﻿Maximum pruning in the tree.

Accepted Answer

### A. Draw a tree showing how a brute-force enumeration algorithm enumerates the solutions for the following instance: C = {2, 2, 4} M = 4. ∻Explanation∻ ⚹The tree will represent all possible combinations of coins from the set C to sum up to the monetary value M. Each node represents a state with a particular subset of coins, and each edge represents the decision to include or not include a coin in the subset. Feasible solutions are those subsets whose sum equals M, and infeasible solutions are those that do not.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Start with an empty set and at each level of the tree, consider including the next coin in the subset or not. ‖ ‖ ▪ ⋮ Draw branches to represent the decision to include or exclude the next coin. ‖ ‖ ▪ ⋮ Mark nodes with subsets that sum up to M as feasible solutions. ‖ ‖ ▪ ⋮ Mark nodes that exceed M or cannot reach M with the remaining coins as infeasible. ‖ ∻Time Complexity∻ ⚹The brute-force algorithm has a time complexity of O(2^N), where N is the number of coins, as it explores every possible combination.⚹ ∻Space Complexity∻ ⚹The space complexity is O(N) due to the depth of the recursion tree.⚹ ### B. Suggest a backtracking strategy to improve the running time of the brute-force algorithm. ∻Explanation∻ ⚹Backtracking is an optimization over the brute-force approach that involves making decisions one at a time and undoing these decisions (backtracking) when we determine that they lead to infeasible solutions.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Start with an empty subset and a target sum M. ‖ ‖ ▪ ⋮ Recursively try to include each coin in the subset. ‖ ‖ ▪ ⋮ After including a coin, decrease the target sum by the value of the coin. ‖ ‖ ▪ ⋮ If the target sum becomes negative, backtrack and try the next possibility. ‖ ‖ ▪ ⋮ If the target sum reaches zero, record the current subset as a solution. ‖ ‖ ▪ ⋮ Continue exploring other possibilities by including or excluding the next coin. ‖ ∻Time Complexity∻ ⚹The time complexity is still exponential in the worst case but is generally better than O(2^N) due to pruning of the search space.⚹ ∻Space Complexity∻ ⚹The space complexity remains O(N) due to the depth of the recursion tree.⚹ ### C. Provide an example of values for C {at least 4} and M that will lead to: #### 1. No pruning in the tree. ∻Explanation∻ ⚹A scenario with no pruning would occur when all subsets need to be explored to determine the solution, typically when M is larger than the sum of all coins in C.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Choose a set C where the sum of all coins is less than M. ‖ ‖ ▪ ⋮ Ensure that no early decisions lead to a sum greater than M. ‖ ‖ ▪ ⋮ Example: C = {1, 2, 3, 4} and M = 11. ‖ ∻Time Complexity∻ ⚹The time complexity is O(2^N) as all subsets are explored.⚹ ∻Space Complexity∻ ⚹The space complexity is O(N) due to the depth of the recursion tree.⚹ #### 2. Maximum pruning in the tree. ∻Explanation∻ ⚹Maximum pruning occurs when the backtracking algorithm can eliminate many branches early in the search process, typically when there are larger coins that quickly exceed M.⚹ ∻Step-by-step Instruction∻ ‖ ▪ ⋮ Choose a set C with at least one coin larger than M. ‖ ‖ ▪ ⋮ Include smaller coins that can combine in limited ways to reach M. ‖ ‖ ▪ ⋮ Example: C = {1, 2, 5, 10} and M = 7. ‖ ∻Time Complexity∻ ⚹The time complexity is better than O(2^N) due to early pruning.⚹ ∻Space Complexity∻ ⚹The space complexity is O(N) due to the depth of the recursion tree.⚹

Sia