---

Mastering Clojure's Change-Making Algorithm: A Deep Dive into Optimal Solutions

The change-making problem is a classic algorithmic challenge that asks for the minimum number of coins to represent a specific amount. In Clojure, this can be solved elegantly using a functional approach, often leveraging breadth-first search (BFS) on the problem space to guarantee an optimal solution for any coin system.

You've probably faced it in real life: a customer pays with a large bill, and you need to give back change. You instinctively grab the largest denomination coins first. But is that always the most efficient way? What if your coin system is unusual? This challenge, a cornerstone of algorithmic thinking, forces us to move beyond simple "greedy" solutions and explore more robust, guaranteed methods. In this guide, we'll dissect this fascinating problem and build an elegant, functional solution in Clojure that is both powerful and insightful.

---

What is the Change-Making Problem?

At its core, the Change-Making Problem is an optimization puzzle. Given a target amount of change and a set of available coin denominations, the goal is to find the combination of coins that sums to the target amount using the fewest possible number of individual coins. It sounds simple, but the complexity lies in guaranteeing that the solution is truly optimal.

For example, if you need to give 40 cents in change and you have pennies (1), nickels (5), dimes (10), and quarters (25), the optimal solution is one quarter, one dime, and one nickel ([25, 10, 5]), for a total of three coins. A non-optimal solution might be four dimes ([10, 10, 10, 10]) or 40 pennies, both of which are valid sums but use more coins.

Canonical vs. Non-Canonical Coin Systems

The difficulty of the problem changes dramatically based on the available coin denominations. Most real-world currency systems, like the US Dollar or the Euro, are canonical (or standard). In a canonical system, a simple greedy algorithm—always picking the largest coin denomination that is less than or equal to the remaining amount—will always yield the optimal solution.

However, consider a non-canonical system with coin values of [1, 3, 4]. If you need to make change for 6, a greedy algorithm would work as follows:

• Pick the largest coin less than or equal to 6: a 4. Remaining amount: 2.
• Pick the largest coin less than or equal to 2: a 1. Remaining amount: 1.
• Pick the largest coin less than or equal to 1: a 1. Remaining amount: 0.

The greedy solution is [4, 1, 1], which uses three coins. However, the truly optimal solution is two coins of value 3, [3, 3]. The greedy approach failed. This is why we need a more powerful algorithm that explores all possibilities intelligently, which is where graph traversal algorithms like Breadth-First Search (BFS) come into play.

---

Why is This a Foundational Problem in Computer Science?

The change-making problem isn't just a theoretical puzzle; it's a gateway to understanding a whole class of optimization and algorithmic problems. Its importance stems from several key areas:

• Algorithmic Paradigms: It serves as a perfect introductory example for teaching different algorithmic strategies, including greedy algorithms, dynamic programming, and graph traversal.
• Optimization Theory: It is a variation of the more general unbounded knapsack problem and the integer linear programming problem, both of which have vast applications in logistics, finance, and resource allocation.
• Technical Interviews: It's a frequent guest in technical interviews for software engineering roles because it tests a candidate's ability to identify edge cases (like non-canonical systems), analyze algorithmic trade-offs (time vs. space complexity), and implement a robust solution.

Solving it in a functional language like Clojure adds another layer of learning, encouraging stateless thinking and the use of powerful abstractions like higher-order functions and lazy sequences. Master the fundamentals with our complete Clojure guide to build a strong foundation for tackling such problems.

---

How to Solve the Change-Making Problem in Clojure

We'll model this problem as a search on a graph. Imagine each possible amount of change from our target down to zero is a node. An edge exists between two nodes if you can get from one to the other by subtracting a valid coin value. Our goal is to find the shortest path from the `target` node to the `0` node. Breadth-First Search (BFS) is the perfect algorithm for finding the shortest path in an unweighted graph.

Here’s the high-level plan for our BFS approach:

1. Start with a set of "edges" or "frontiers" to explore, which initially contains only the target amount.
2. Maintain a "graph" or a map of visited nodes to track the path. This prevents cycles and redundant work.
3. In each step (level of the search), generate new frontiers by subtracting every available coin from the current frontiers.
4. Continue this process level by level until one of the frontiers becomes 0.
5. Once 0 is reached, reconstruct the path from 0 back to the target amount using the graph to find the coins used.

Visualizing the BFS Algorithm

Let's visualize the process for a target of 6 with coins [1, 3, 4].

● Start (Target = 6)
│
└─── Level 0: {6}
     │
     ▼
┌──────────────────┐
│ Subtract coins   │
│ (6-1), (6-3), (6-4)│
└────────┬─────────┘
         │
         ▼
● Level 1: {5, 3, 2}
│
├─── From 5 → {4, 2, 1}
├─── From 3 → {2, 0}  ← BINGO! Path found.
└─── From 2 → {1, -1, -2}
     │
     ▼
┌──────────────────┐
│ Path to 0 found: │
│ 6 → 3 → 0        │
│ Coins: (6-3)=3, (3-3)=3 │
└────────┬─────────┘
         │
         ▼
● End (Result: [3, 3])

---

Where the Provided Clojure Solution Shines: A Detailed Code Walkthrough

The solution from the kodikra module is a masterclass in functional programming. It elegantly implements the BFS strategy using higher-order functions, lazy sequences, and immutable data structures. Let's break down the code from the `change.clj` file piece by piece.

(ns change)

(defn- find-decrements
  "Returns an iterable function that takes a vector pair of [edges graph]
  and returns a pair of [new-edges new-graph], where the new edges
  are obtained by subtracting all coins from all edges, removing any
  that are already in the graph or negative values."
  [coins]
  (fn [[edges graph]]
    (let [new-edges (->> (for [edge edges coin coins]
                           (let [new-edge (- edge coin)]
                             (when (and (not (neg? new-edge))
                                        (not (contains? graph new-edge)))
                               [new-edge edge])))
                         (remove nil?)
                         (into {}))
          new-graph (into graph new-edges)]
      [(keys new-edges) new-graph])))

(defn issue
  "Returns the smallest combination of coins for a given total"
  [total coins]
  (cond
    (neg? total) (throw (IllegalArgumentException. "cannot change a negative total"))
    (zero? total) []
    :else
    (let [decrements (find-decrements coins)
          path-graph (->> [[total] {total nil}]
                          (iterate decrements)
                          (drop-while (complement (some zero? (first %))))
                          (first)
                          (second))]
      (when (contains? path-graph 0)
        (->> (iterate path-graph 0)
             (take-while identity)
             (butlast)
             (map (fn [parent child] (- child parent)) (rest))
             (sort))))))

The Engine Room: `find-decrements`

This is a higher-order function—it's a function that *returns another function*. This is a powerful pattern in Clojure for creating configurable, reusable logic.

• (defn- find-decrements [coins]): It takes the list of `coins` as an argument and returns a new anonymous function that will perform one step of our BFS. This inner function is what `iterate` will call repeatedly.
• (fn [[edges graph]]): The returned function takes the current state as an argument, which is a vector containing the current `edges` (the amounts to explore, our frontier) and the `graph` (a map of `child -> parent` tracking all visited amounts).
• (for [edge edges coin coins] ...): This is the core logic. It's a nested loop that iterates through every current `edge` and every `coin`. For each pair, it calculates `new-edge` by subtracting the coin value.
• (when (and (not (neg? new-edge)) (not (contains? graph new-edge)))): This is our guard condition. It ensures we only consider valid new edges: they must not be negative, and they must not have been visited before (i.e., not already in our `graph`).
• [new-edge edge]: If the new edge is valid, it creates a pair: `[child parent]`. This is crucial for reconstructing the path later.
• (->> ... (remove nil?) (into {})): The `for` comprehension produces `nil` for invalid subtractions. `(remove nil?)` cleans these up. `(into {})` then converts the list of `[child parent]` pairs into a map, which efficiently creates our `new-edges` map for this level. Duplicates are automatically handled.
• (let [new-edges ... new-graph ...] [ (keys new-edges) new-graph ]): Finally, it calculates the `new-graph` by merging the old graph with the new edges map. It then returns the next state: a vector containing just the keys of the new edges (our next frontier to explore) and the fully updated graph.

The Conductor: `issue`

This is the main public function that orchestrates the entire process.

• Edge Cases: It first handles the base cases. A negative `total` is invalid and throws an exception. A `total` of zero requires no coins, so it returns an empty list `[]`.
• (let [decrements (find-decrements coins) ...]): It starts by creating our state-transition function, `decrements`, by calling `find-decrements` with the available coins.
• The `->>` (Thread-Last) Macro: This is where the magic happens. Let's break down this pipeline.
  1. [[total] {total nil}]: This is the initial state for our BFS. The frontiers `edges` start as a list containing just the `total`, and the `graph` starts as a map with the `total` pointing to `nil` (since it has no parent).
  2. (iterate decrements): This is the heart of the algorithm. `iterate` takes our state-transition function `decrements` and our initial state, and it creates a *lazy (infinite) sequence* of states. It looks like `[state_0, state_1, state_2, ...]`, where `state_1` is the result of `(decrements state_0)`, `state_2` is `(decrements state_1)`, and so on. This lazily generates the levels of our BFS without consuming infinite memory.
  3. (drop-while (complement (some zero? (first %)))): This is our stopping condition. It drops states from the lazy sequence *while* the condition is true. The condition checks if the list of `edges` (the `first` element of the state `%`) contains a zero. `some zero?` returns `true` if it does. `complement` inverts this. So, we keep dropping states as long as they *don't* contain a zero in their edge list.
  4. (first): Once `drop-while` stops, it means we've found the first state where `0` is reachable. We take this state.
  5. (second): This state is a vector `[edges graph]`. We only care about the `graph`, which is the `second` element. We now have our complete `path-graph` that contains the shortest path from `total` to `0`.

Data Flow within the `iterate` Pipeline

    ● Initial State
      [[total], {total: nil}]
      │
      ▼
  ┌──────────────────┐
  │   iterate        │
  │ (decrements)     │ Creates a lazy sequence of states
  └────────┬─────────┘
           │
           ├─ State 0: [[total], {total: nil}]
           │
           ├─ State 1: [[total-c1, total-c2], {total:nil, t-c1:total, ...}]
           │
           ├─ State 2: [...]
           │
           └─ ...
           │
           ▼
  ┌──────────────────┐
  │   drop-while     │ Skips states until `0` is found in the edges list
  └────────┬─────────┘
           │
           ▼
    ● First State containing `0`
      [[..., 0, ...], {..., 0:parent_of_0, ...}]
      │
      ▼
  ┌──────────────────┐
  │ (first) then     │
  │ (second)         │ Selects this state, then extracts the graph map
  └────────┬─────────┘
           │
           ▼
    ● Final `path-graph`
      {0:p1, p1:p2, ..., total:nil}

Path Reconstruction

Once we have the `path-graph`, the final part of the `issue` function reconstructs the list of coins.

• (when (contains? path-graph 0) ...): This is a safety check. If `0` isn't in the graph, it means no solution was found (e.g., trying to make change for 3 with only coins of [5, 10]). In this case, it returns `nil`.
• (->> (iterate path-graph 0) ...): We use another `iterate`! This time, since a map in Clojure can be used as a function to look up its keys, `(iterate path-graph 0)` generates a sequence by starting with `0` and repeatedly looking up the current value in the graph to find its parent. This traces the path backwards: `(0, parent_of_0, parent_of_parent_of_0, ..., total, nil)`.
• (take-while identity): The sequence ends with `nil`. `identity` returns the value itself, and `take-while` stops when it encounters a "falsy" value (like `nil`). This cleanly chops off the end of the sequence.
• (butlast): We now have `(0, p1, p2, ..., total)`. We don't need the `0`, so `butlast` removes it. The path is now `(p1, p2, ..., total)`.
• (map (fn [parent child] (- child parent)) (rest)): This is a clever trick. We `map` over the path and its `rest` (the path shifted by one). This gives us pairs of `(parent, child)` for each step. For example, if the path is `(3, 6)`, `rest` is `(6)`. The map gets `(parent=3, child=6)` and calculates `(- 6 3)` to get the coin `3`. This reconstructs all the coins used along the path.
• (sort): Finally, the problem requires the coins to be sorted, so we sort the resulting list.

---

When to Use a Different Approach: Dynamic Programming

While the BFS solution is correct and elegant, another common and powerful technique for solving this problem is Dynamic Programming (DP). A DP approach builds the solution from the bottom up.

The core idea is to solve the problem for every amount from 1 up to the target `total`. We can use an array, say `dp`, where `dp[i]` stores the minimum number of coins required to make change for amount `i`.

The recurrence relation would be: dp[i] = min(dp[i - coin] + 1) for all `coin` in `coins` where `i >= coin`.

In simpler terms, to find the minimum coins for amount `i`, we look at all the solutions we've already found for smaller amounts (`i - coin`) and take the best one, adding one more coin (the `coin` we just used).

Algorithm Comparison

To provide a clearer picture, here's a comparison of the approaches we've discussed. This is crucial for making informed decisions in a real-world engineering context.

Approach	Pros	Cons	When to Use
Greedy Algorithm	- Extremely simple to implement. - Very fast (linear time complexity).	- Only works for canonical coin systems. - Will produce incorrect (non-optimal) results for many coin sets.	When you are 100% certain the coin system is canonical and performance is the absolute top priority.
BFS (Graph Search)	- Guaranteed to find the optimal solution. - Conceptually clear (shortest path in a graph). - Clojure implementation is elegant with lazy sequences.	- Can have high memory usage as it needs to store the visited nodes graph. - Might explore many unnecessary paths for large totals.	A great general-purpose solution. Perfect for scenarios where correctness is mandatory and the state space is not astronomically large.
Dynamic Programming	- Guaranteed to find the optimal solution. - Very efficient time complexity. - Often more intuitive for those familiar with bottom-up approaches.	- Requires space proportional to the target amount (e.g., an array of size `total`). - Can be less memory-efficient than BFS if the number of reachable states is small but the total is large.	Excellent for when the target amount is reasonably sized and you need a highly performant, systematic solution. Often a go-to for competitive programming.

This kind of deep algorithmic analysis is a key part of the curriculum you will find in our comprehensive Clojure Learning Path, which prepares you not just to write code, but to engineer effective solutions.

---

Frequently Asked Questions (FAQ)

Why does the greedy algorithm fail for some coin sets?

The greedy algorithm makes a locally optimal choice at each step (picking the biggest coin possible) without considering the global picture. For a non-canonical system like [1, 3, 4] and a target of 6, picking 4 first prevents you from using the globally optimal solution of two 3s. It gets stuck in a suboptimal path.

Is this Clojure BFS solution the most performant?

It depends. For time complexity, a well-implemented Dynamic Programming solution is often faster. However, the BFS solution's use of lazy sequences in Clojure makes it very memory efficient in how it explores the state space. Its performance is generally very good for a wide range of practical inputs. The "best" solution always depends on the specific constraints of the problem (e.g., size of total, number of coins).

What exactly is a "canonical coin system"?

A canonical coin system is a set of denominations for which the greedy algorithm is guaranteed to produce an optimal solution for any amount. Most real-world currencies are designed to be canonical for ease of use. There are mathematical tests to determine if a system is canonical, but for practical purposes, it's safer to use an algorithm like BFS or DP that works for all systems.

How does this problem relate to dynamic programming?

Both BFS and DP solve this problem by breaking it down into smaller, overlapping subproblems. BFS does this from the "top-down" (from the target amount), while DP typically works from the "bottom-up" (solving for 1, then 2, then 3, etc., up to the target). The underlying principle of solving subproblems to build a final solution is central to both.

Can this code handle very large change amounts?

The primary limitation for very large amounts would be memory. The `path-graph` stores every reachable amount between the total and zero. If the total is in the billions and the coins are small, this map could become excessively large, potentially leading to an `OutOfMemoryError`. For such cases, more advanced algorithms or memory-optimized DP techniques might be necessary.

What is the role of `iterate` in this Clojure solution?

iterate is a core Clojure function that creates a lazy (potentially infinite) sequence by repeatedly applying a function to its previous result. Here, it's used to generate the successive states of the BFS search without calculating them all at once, which is highly memory-efficient. It drives the entire search process in a purely functional way.

Are there other real-world applications of this algorithm?

Absolutely. The underlying principle of finding the optimal combination of items to reach a target value is found in many domains. This includes resource allocation (finding the cheapest way to procure materials), network routing (finding the shortest path in a network, where coins are edge weights), and even computational finance (portfolio optimization).

---

Conclusion and Future-Proofing Your Skills

We've journeyed from a simple real-world problem to a deep, functional implementation in Clojure. The change-making problem beautifully illustrates the need to look beyond the obvious "greedy" solution and embrace more robust algorithms like Breadth-First Search. The provided solution from the kodikra.com learning path is a testament to Clojure's power, using lazy sequences and higher-order functions to create a solution that is not only correct but also concise and deeply expressive.

Understanding these different algorithmic trade-offs—Greedy vs. BFS vs. Dynamic Programming—is what separates a coder from a true software engineer. As technology evolves, the principles of optimization and algorithmic efficiency remain timeless. Languages like Clojure, running on the robust and ever-improving JVM (benefiting from advancements in Java 21 and beyond), provide the perfect platform to build scalable, correct, and maintainable systems grounded in these powerful ideas.

Disclaimer: The code and explanations in this article are based on modern Clojure (1.11+) and its standard library. The fundamental concepts, however, are language-agnostic and will remain relevant for years to come.

---

Published by Kodikra — Your trusted Clojure learning resource.