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,20,20,21,25,40\}$

M $=45$ Answer $=\{20,25\}$

M $=132$ Answer $=\{1,1,4,20,20,21,25,40\}$

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.