DSA Perfect Squares

The problem

A perfect square is a whole number multiplied by itself, like 1, 4, and 9. The Perfect Squares problem asks for the fewest perfect squares that sum to a target number.

Every square may be used more than once. The answer is a count, and the article also recovers one split that reaches it.

cases = [
    (12, 3),
    (13, 2),
    (18, 2),
    (23, 4),
    (30, 3),
]
for n, expected in cases:
    print("target", n, "fewest squares:", expected)

Read the first row with care. Target 12 takes three squares, all of them 4. Taking the biggest square first does worse, as the next section shows.

Intuition: take the largest square that fits

The first idea takes the largest square at or below the target. It then repeats on what remains. The method is quick and it always reaches the target, because square 1 always fits.

def greedy(n):
    parts = []
    k = 1
    squares = []
    while k * k <= n:
        squares.append(k * k)
        k += 1
    rest = n
    for sq in reversed(squares):
        while rest >= sq:
            parts.append(sq)
            rest -= sq
    return parts

parts = greedy(12)
print("greedy split for 12:", parts)
print("greedy count:", len(parts))
print("better split: [4, 4, 4] count: 3")

Greedy takes 9 first and pays for it. Three ones must fill the rest. The better split skips 9 and uses three squares of 4.

Brute force: try every last square, recounting targets

The brute force picks the last square of the target. Each fitting square leaves a smaller target, and that target is solved from scratch. No answer is stored, so the same small target is solved many times.

calls = 0

def fewest(n):
    global calls
    calls += 1
    if n == 0:
        return 0
    best = n
    k = 1
    while k * k <= n:
        best = min(best, 1 + fewest(n - k * k))
        k += 1
    return best

for n in [12, 15, 18]:
    calls = 0
    result = fewest(n)
    print("target", n, "fewest:", result, "calls:", calls)

Even these small targets cost many calls. Most calls repeat a target that another branch already solved. A table stores each answer once.

The optimal solution: one table of fewest counts

The state is dp(n), the fewest perfect squares that sum to n. Each target tries every square that fits as its last square, and dp(n) is one plus the smallest count before it.

The table starts with dp(0) equal to 0. Zero needs no squares. Each later count builds only on smaller counts, which are already final.

def square_table(limit):
    squares = []
    k = 1
    while k * k <= limit:
        squares.append(k * k)
        k += 1
    dp = [0] * (limit + 1)
    for n in range(1, limit + 1):
        dp[n] = 1 + min(dp[n - sq] for sq in squares if sq <= n)
    return squares, dp

def recover(dp, squares, n):
    parts = []
    while n > 0:
        for sq in sorted(squares, reverse=True):
            if sq <= n and dp[n - sq] == dp[n] - 1:
                parts.append(sq)
                n -= sq
                break
    return parts

squares, dp = square_table(30)
cases = [(12, 3), (13, 2), (18, 2), (23, 4), (30, 3)]
for n, expected in cases:
    print("target", n, "->", dp[n], "split:", recover(dp, squares, n), "match:", dp[n] == expected)

All five cases from the start of the article pass. The recovered splits prove each count. A count alone would leave the reader trusting the table.

Walkthrough: building the table up to 13

The walk fills one target at a time. Each row shows the squares that fit and the earlier counts they point to.

squares = [1, 4, 9]
dp = [0]
print("dp(0) = 0")
for n in range(1, 14):
    fitting = [sq for sq in squares if sq <= n]
    earlier = [dp[n - sq] for sq in fitting]
    dp.append(1 + min(earlier))
    print("target", n, "fitting:", fitting, "earlier counts:", earlier, "dp:", dp[n])
print("answer for 13:", dp[13])

The last row reads the answer off the table. Target 13 points back to counts 3, 1, and 1. The smallest gives dp(13) equal to 2, from 9 plus 4.

Complexity

The table tries each fitting square once per target, so its time is O(n times the square root of n). The table holds one count per target, so its space is O(n).

import math

calls = 0

def fewest(n):
    global calls
    calls += 1
    if n == 0:
        return 0
    best = n
    k = 1
    while k * k <= n:
        best = min(best, 1 + fewest(n - k * k))
        k += 1
    return best

for n in [10, 13, 16]:
    calls = 0
    fewest(n)
    tries = sum(int(math.isqrt(m)) for m in range(1, n + 1))
    print("target", n, "- brute calls:", calls, " table inner tries:", tries)

The brute calls already dwarf the table tries at target 16. The gap grows with the target. Stored answers are the whole saving.

Edge cases and pitfalls

Target zero needs no squares at all. A target that is itself a square answers 1. Small targets below 4 can only use square 1, so their counts equal the target.

def fewest_table(limit):
    squares = []
    k = 1
    while k * k <= limit:
        squares.append(k * k)
        k += 1
    dp = [0] * (limit + 1)
    for n in range(1, limit + 1):
        dp[n] = 1 + min(dp[n - sq] for sq in squares if sq <= n)
    return dp

dp = fewest_table(30)
print("zero:", dp[0])
print("one:", dp[1])
print("three, only ones fit:", dp[3])
print("a square itself, 25:", dp[25])
print("greedy trap, 12:", dp[12])
print("one past a square, 26:", dp[26])

The classic pitfall is the greedy split from the intuition section. It always works and it is sometimes one square too many. The table avoids it by trying every fitting last square.