Perfect Squares
Perfect Squares is LeetCode 279 (Medium). You are given a positive integer n. Return the smallest number of perfect squares that add up to exactly n.
- A perfect square is the square of a whole number: 1, 4, 9, 16, 25 and so on.
- The same square may be used as many times as you like.
- Only the count matters; you do not return which squares were used.
n is at most 10⁴. There are at most 100 squares below that bound, so trying every square for every value up to n is about a million steps, which is the budget the intended solution fits in.
- 1 <= n <= 10⁴
Intuition
Taking the largest square that fits looks right, but it can leave a remainder that is expensive to finish, so no single choice can be trusted. Look at the problem from the other end instead.
Whatever the best sum for n is, it has some last square s. Remove it and what is left, n − s, must itself use as few squares as possible, or swapping in a cheaper sum would beat the optimum. So the answer for n is 1 plus the best answer for n − s, minimised over every square s ≤ n. Every n − s is smaller than n, so solving 0, 1, 2, … in order has each answer ready before it is needed.
"Fewest pieces that add up to a target, any piece reusable" is unbounded knapsack, the same shape as Coin Change with the coins fixed to 1, 4, 9, 16 and so on. When a greedy pick looks tempting but the piece values do not divide each other, expect a counterexample and reach for the DP.
Approach
Before reading on, work out by hand the fewest squares for 1 through 13 and see where greedy first gives the wrong count. Then write the recurrence that turns your table into code. Aim for O(n√n).
Two ways to solve it
Fill dp[i] for every i from 1 to n, trying each square as the last one.
- Code: two short loops, no data structures.
- Proof: follows straight from the recurrence.
- Bonus: answers every value up to
n.
The one to write first in an interview.
Treat each number as a node and subtracting a square as an edge, then search level by level from n towards 0.
- Stops early: at the first level that reaches 0.
- Needs: a queue and a visited set.
- Worst case: no better than the DP.
Often faster in practice, more code.
Both do O(n√n) work in the worst case, but the DP is shorter and easier to prove correct. The steps, code and live demo below follow the DP; the BFS code comes after the demo.
Set up the table
Make dp of size n + 1, where dp[i] is the fewest squares that sum to i. Set dp[0] = 0, because the empty sum needs no squares, and every other entry to n, a safe ceiling since i ones always work.
Try every square as the last one
For each i from 1 to n, loop over the squares s ≤ i and keep dp[i] = min(dp[i], dp[i − s] + 1). The + 1 pays for s itself, and dp[i − s] is already the cheapest way to make the rest.
Fill the table in increasing order
Going from i = 1 upward guarantees every dp[i − s] is final before it is read. List the squares once up front and stop the inner loop at the first one larger than i; that keeps a perfect squares Python solution near 10⁶ simple steps for n = 10⁴.
Return dp[n]
After the loop, dp[n] is the answer. It can never stay at the ceiling: 1 is a square, so every value is at most one more than the value just below it, and the answer is never -1.
Perfect Squares solution in Python | C++ | Java
BFS on remainders
Each level subtracts one more square from every remainder in the frontier. The first level where a remainder is itself a square is the fewest squares needed.
Common pitfalls
Taking the largest square first
while n:
s = int(n**0.5) ** 2
n -= s
count += 1for sq in squares:
if sq > i:
break
dp[i] = min(dp[i], dp[i - sq] + 1)Greedy gives 9 + 1 + 1 + 1 for 12 (four) when 4 + 4 + 4 (three) exists. Squares are not multiples of each other, so the largest choice can leave a remainder that is expensive to finish.
Leaving dp[0] at the upper bound
dp = [n] * (n + 1)
dp = [0] + [n] * n
Every exact square i is found through dp[i − i] + 1. If dp[0] is n, then dp[0] + 1 is n + 1, so dp[4] stays at n instead of 1, and every later value built on it is wrong.
Recursing on n without a memo
def f(n):
return 1 + min(f(n - s) for s in squares if s <= n)@cache
def f(n):
...The same remainders are reached through many different orders of squares, so plain recursion is exponential. The memo, or the bottom-up table, makes each value cost √n once.
Complexity
Perfect Squares FAQ
What is the largest possible answer?
4. Lagrange's four-square theorem says every positive integer is a sum of at most four squares, and Legendre's three-square theorem says exactly the numbers of the form 4ᵃ(8b + 7), such as 7, need all four. Those two facts give an O(√n) maths solution: return 1 if n is a square, 2 if n − k² is a square for some k, 4 for the 4ᵃ(8b + 7) form, else 3.
How is perfect squares LeetCode 279 related to Coin Change?
It is Coin Change (LeetCode 322) where the coins are 1, 4, 9, 16 and so on, the same unbounded knapsack. Because 1 is always a coin, every amount is reachable, so unlike Coin Change the answer is never -1.