• 1 <= n <= 10⁴
• Squares may be repeated freely.
• Only the count is returned, not the squares themselves.
• Order does not matter: 4 + 9 and 9 + 4 are the same answer of 2.

There is no grid here, no words, no puzzle — just a number. Which makes this a good place to test whether the shortest-path idea is really about grids, or about something more general.

Reword the question. You are standing on the number n. A move subtracts any perfect square that does not overshoot. From 12 you may move to 11 by subtracting 1, to 8 by subtracting 4, or to 3 by subtracting 9. Repeat until you land exactly on 0. The number of squares used is the number of moves made, so the fewest squares summing to n and the fewest moves from n down to 0 are the same question.

That is a graph, once you accept that a graph does not need to be drawn or stored:

That last property is what makes this tractable, and it is worth pausing on. The size of the square subtracted does not affect the price. A big jump and a small jump cost the same. So the problem is unweighted, and unweighted shortest paths are the easy kind.

Notice something else: the graph has at most n + 1 nodes and each has at most √n outgoing edges, since the squares that fit under n are 1², 2², … up to ⌊√n⌋². For n = 10⁴ that is 10,001 nodes with at most 100 edges each — about a million transitions. Entirely affordable. Sizing the space like this before choosing an algorithm tells you an exhaustive search is on the table.

Written directly, "try every square and take the best" is a few lines.

def num_squares(n):
    if n == 0:
        return 0
    best = n                                # worst case: n copies of 1
    s = 1
    while s * s <= n:
        best = min(best, 1 + num_squares(n - s * s))
        s += 1
    return best

Correct, and unusably slow. The reason is not the branching by itself but the repetition. Reaching 8 by subtracting 4 from 12, and reaching 8 by subtracting 1 from 9 which came from 10 which came from 12, are different histories arriving at the identical situation — and the identical situation has an identical answer. How you got to a number tells you nothing about the best way forward from it. The plain recursion re-derives the answer for 8 every time it arrives there, and the same for every other value, so the work multiplies exponentially.

That observation — the future depends only on the current state, never on the route taken to it — is exactly what licenses visiting each state once and only once. Which is what the next approach does.

Explore by distance rather than by depth. Layer 1 is every value reachable from n in one subtraction. Layer 2 is every unclaimed value reachable from layer 1. And so on. A value first appears in the layer equal to the minimum number of squares needed to get from n down to it — earlier is impossible, and later cannot happen because the moment a layer-d value is expanded, all of its unclaimed successors are claimed for layer d+1.

Consequently the first time 0 appears, the layer number is the answer, and the search stops. No comparing of alternatives, no best-so-far. Discovery order is answer order. This is Breadth-First Search, and it wants a queue — a structure returning values in the order they were found. FIFO ordering is what keeps layer d fully processed before layer d+1 begins; a stack would plunge down one chain of subtractions and the first arrival at 0 would be some answer rather than the smallest.

The other essential piece is a visited set, and here it is not merely an optimisation. Without it the search would revisit values endlessly and never finish in reasonable time. With it, each of the n+1 values is expanded at most once.

from collections import deque

def num_squares(n):
    squares = [i * i for i in range(1, int(n ** 0.5) + 1)]
    queue = deque([(n, 0)])                 # remaining amount, squares used
    visited = {n}

    while queue:
        remaining, used = queue.popleft()
        for s in squares:
            nxt = remaining - s
            if nxt == 0:
                return used + 1             # first arrival at 0 is optimal
            if nxt > 0 and nxt not in visited:
                visited.add(nxt)            # claim on discovery, not on removal
                queue.append((nxt, used + 1))
    return n

Since the squares list is sorted ascending, the loop tries the smallest subtraction first. That does not affect correctness — every square in the layer is tried before the layer ends — it just means the trace below explores in a predictable order.

Work: at most n values, each with at most √n successors, so O(n√n) time and O(n) memory.

Squares that fit: 1, 4, 9.

The route was 12 → 8 → 4 → 0, subtracting 4 each time, which is precisely 12 = 4 + 4 + 4. The greedy route that grabs 9 first reaches 3, then 2, then 1, then 0 — four terms — and BFS simply never gets there first, because it finishes all of layer 3 before considering anything at depth 4.

For n = 7 the same process runs: layer 1 gives 6 and 3, layer 2 gives 5, 2 and 2 again, layer 3 gives 4 and 1, and layer 4 reaches 0 from 4 by subtracting 4 or from 1 by subtracting 1. The answer is 4, matching 4 + 1 + 1 + 1.

Because the future depends only on the current value, this can equally be solved by filling a table from the bottom up. Let dp[x] be the answer for x. Then dp[0] is 0, and for every other x, dp[x] is one more than the best dp[x - s] over all squares s that fit.

def num_squares(n):
    dp = [0] + [float("inf")] * n
    for x in range(1, n + 1):
        s = 1
        while s * s <= x:
            dp[x] = min(dp[x], dp[x - s * s] + 1)
            s += 1
    return dp[n]

This is O(n√n) as well — the same bound, and no wonder: it visits the same nodes and the same edges. It is the same graph traversed in a different order, computing every value rather than stopping at the first arrival. BFS can quit the moment it reaches 0, so it often touches less; the table is simpler to write and answers every value from 1 to n as a by-product. Either is a fine answer, and being able to say they are the same graph is what an interviewer is listening for.

There is also a closed-form curiosity worth knowing. Lagrange's four-square theorem proves every positive integer is the sum of at most four squares, so the answer is always 1, 2, 3 or 4 — never more. That is why n = 7 needing 4 is the worst case rather than an outlier. Testing 1 is a perfect-square check, 4 happens exactly when n has the form 4^a(8b + 7), and 2 can be tested by trying every square below n and checking whether the difference is a square; anything left over is 3. That gives an O(√n) solution, but it rests on a number-theory result rather than on any search idea, so lead with the graph and mention this as an aside.

The nodes here were plain integers, the edges were arithmetic, and nothing was ever stored as a graph. That is the point. A graph is a set of states plus a rule for moving between them, and the states can be anything a problem describes — a cell, a word, a lock code, a remaining amount.

Train the reflex: when a problem asks for the fewest operations to get from one value to another, and every operation counts the same, define the state, define the moves, and run BFS. And when the plain recursion looks exponential, check whether different histories can arrive at the same state — if they can, that state deserves to be computed once, whether you enforce that with a visited set or a table.