A Complete Combinatorial Solution for a Coins Change Puzzle and Its Computer Implementation

Abstract

In this paper, we study a combinatorial problem encountered in monetary systems. The problem concerned is to find an optimal solution R(k; n) of a combinatorial problem for some positive integers k and n. To the authors' knowledge, there is no eficient solutions for this problem in the literatures so far. We first show how to find an eficient recursive construction algorithm based on the backtracking search strategy. Furthermore, we can give an explicit formula for finding the maximal elements of the solution. Our new techniques have improved the time complexities of the search algorithm dramatically.