How to optimize a recursive tree traversal?

Question

I recently discussed the following (quite basic) problem with a colleague and would like to know how to optimize it and what runtime the optimized version would have.

Problem:

You have to return an amount of money with a set of coins available. You have an unlimited number of coins available. If it is not possible to return this amount you should return an error.

Example 1:

Set of coins (EUR in this case, in ct) {200, 100, 50, 20, 10, 5, 2, 1}, amount to return 99.

Answer: 50, 20, 20, 5, 2, 2

Example 2:

Set of coins {50, 20, 2}, amount to return 99.

Answer: no solution found! (obviously, since there is no way to return an odd number!).

My Solution:

(code at the end of this post). My solution is a recursive function that is greedy but will try to use smaller coins if the greedy approach does not work. In the end, I am basically traversing the solution space (a tree) in a depth-first manner.

In the worst case (e.g. {97, 98, 99} and 300) no solution is found and I have to traverse the entire tree, which results in O(l^(a\s)), where l is the length of the set of coins (8 in the case of EUR, 3 in this case), a is the amount (300 in the examples), s is the smallest coin available (97 in this example) and \ is integer division. Please correct me if I am wrong.

Optimization that I am looking for:

You can see that there are some paths in the "solution tree" that are unnecessary to explore. This is, because the order of the coins does not matter, but different orders are still traversed (e.g. 99, 98, 97 and 98, 99, 97 are both traversed). How can I prune the tree in such a way that only the necessary paths are traversed? I was thinking about some kind of caching, but am unable to come up with something smart. What would the runtime of such a solution be?

C++17 Code:

#include <iostream>
#include <list>
#include <optional>
#include <string>
std::string print_list(std::optional<std::list<int>> lst)
{
 if (lst)
 {
 std::string res = "";
 for (int num : lst.value())
 {
 res += std::to_string(num) + ", ";
 }
 return res + "\n";
 }
 return "no solution found!\n";
}
std::optional<std::list<int>> get_coins(int remainder, std::list<int> &currency, std::list<int> coins)
{
 if (remainder == 0)
 {
 return std::optional{coins};
 }
 for (int coin : currency)
 {
 if (coin <= remainder)
 {
 coins.push_back(coin);
 auto result = get_coins(remainder - coin, currency, coins);
 if (result)
 {
 return result;
 }
 }
 }
 return std::nullopt;
}
int main()
{
 // Example 1
 std::list<int> eur{200, 100, 50, 20, 10, 5, 2, 1};
 std::cout << print_list(get_coins(99, eur, {})); // 50, 20, 20, 5, 2, 2,
 // Example 2
 std::list<int> fail{50, 20, 2};
 std::cout << print_list(get_coins(99, fail, {})); // no solution found!
}

• Scott Hunter: Why are you searching different orders?
• User12547645: I don`t want to. I just want to keep a greedy approach which always give me a solution if there is one. I search them because I am exploring the entire solution space, not because I want to
• Scott Hunter: You want to solve the problem faster without avoiding the most obvious waste of time: got it.
• Mike Sar: Are you looking ONLY for a solution to this OR also and additional solution that can be different from this, but will do its job and be more efficient than the one you came up with initially? Tip: may try dividing approach(taking the whole part, ignoring the reminder) or use double for(nested; maybe also done with one; I immediately came up with the code for double loop).

Answer 1

That is a classic dynamic programming problem. It can be solved in O(amount to return * number of coin types).

// named vector. A vector of coin values.
struct currency {
 std::vector<int> values;
 int const* begin() const {return values.data();}
 int const* end() const {return values.data()+values.size();}
};
// named map. A map of coin counts
struct coins {
 std::map<int, int> count;
 // helper to remove bounds-checking elsewhere
 void add_coin( int type ) {
 ++count[type];
 }
};
struct coins_required {
 std::vector<std::optional<std::optional<int>>> count = {{0}}; // number of coins required for [i] money
 // outer optional is "have I solved this", inner is "is this possible".
 // save on bounds checking code elsewhere.
 // note, is only trustworthy if someone called solve on i already.
 std::optional<std::optional<int>> operator[](int i) {
 if (count.size() <= i) count.resize(i+1);
 return count[i];
 }
 // finds the number of coins required to make up "i" money
 std::optional<int> solve( int i, currency const& c ) {
 //std::cerr << "Solving for " << i << "\n";
 if (i == 0)
 {
 return 0;
 }
 if ( (*this)[i] )
 {
 //std::cerr << "Answer is: ";
 if (*(*this)[i]) {
 //std::cerr << **(*this)[i] << "\n";
 } else {
 //std::cerr << "no solution\n";
 }
 return *(*this)[i];
 }
 std::optional<int> solution = {};
 for (auto coin:c) {
 if (i < coin) continue;
 std::optional<int> subsolution = solve( i-coin, c );
 if (!subsolution)
 continue;
 if (solution) {
 *solution = (std::min)( *subsolution + 1, *solution );
 } else {
 solution = *subsolution + 1;
 }
 }
 // count[] is safe, as we used *this[] above
 count[i] = solution;
 if (solution)
 {
 //std::cerr << i << " needs " << *solution << " coins\n";
 }
 return solution;
 }
 // returns a vector of coin counts for money value i, given currency c.
 std::optional<coins> get_coins( int i, currency const& c ) {
 if (i==0) return coins{};
 auto count = solve(i, c);
 if (!count) return {}; // no solution
 for (auto coin:c) {
 // can we remove this coin?
 if (coin > i)
 continue;
 // Does removing this coin result in an optimal solution?
 auto subsolution = solve(i-coin, c);
 if (!subsolution || *subsolution +1 > *count)
 continue;
 // recurse! If we hit this, we should be guaranteed a solution.
 auto retval = get_coins( i-coin, c );
 assert(retval); // logically impossible
 if (!retval) continue;
 retval->add_coin(coin);
 return retval;
 }
 assert(false);// logically impossible to reach
 return {};
 }
};

The double optional is funny.

Live example.

Answer 2

I was thinking about some kind of caching

The problem you describe is a classic dynamic programming problem. You simply add a global map to your solution and make your descent a breadth first. One way to do this is to have a "frontier list" a list (or vector) of piles of coins. You will start with 1 pile of coins (the empty list with a value of 0). You also add this to your map. Now you define a function that has two loops. The first loop goes through each of the members of your frontier list, and makes a new list. At the end of the loop, copy the new frontier list over the old one and repeat.
The inner loop adds a coin of each type to the pile of coins. It then calculates the value of the coins, and checks the map to see if that value has already been made. If it has then the existing map entry must use less coins, so skip this new pile.
If it does not, you have made a new value, so add the new pile to your map and also to the new frontier-list. So in pseudo-code.

frontier_list.push_back(Pile{});
while(!map.contains[target_value]) {
 for (const auto& pile: frontier_list)
 for (const auto& coin: coin_list) {
 const auto new_pile = pile + coin;
 const auto value = add_coins(new_pile);
 if (!map.contains(value)) {
 new_frontier_list.push_back(new_pile);
 map[value] = new_pile;
 }
 }
 }
 frontier_list = new_frontier_list;
}

This pseudo-code contains a lot of optimization opportunities, particularly it contains a lot of copying. However, conceptually, this is how you use caching to avoid retracing the same paths.