Optimality of a Greedy Algorithm If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you prove it is optimality?

For example you have a set of numbers $\mathcal{M}=\{1,2,3,4\}$ and you want to design an algorithm to obtain the minimum number of integers required to obtain a sum 5. In this case, $1,4$ or $2,3$ can produce 5 and both are optimal solutions as the minimum number required is two. 

How to prove the optimality of the algorithm ?

I tried by contradiction an assume that there is an optimal solution $P^*$ and my algorithm doesnot produce an optimal solution $P$ so $P \neq P^*$. but I donot know how to continue the argument.
If a greedy algorithm is not always optimal then a counterexample is sufficient proof of this. 

In this case, take $\mathcal{M} = \{1,2,4,5,6\}$. Then for a sum of $9$ the greedy algorithm produces $6+2+1$ but this is not optimal because $5+4$ has fewer summands.