Perfect Squares
Problem
n, return the fewest perfect squares
(1, 4, 9, 16, …) that add up to exactly n. The same square may
be used any number of times.n = 12Output3 (4 + 4 + 4)n = 13Output2 (4 + 9)1 ≤ n ≤ 104
Try it yourself
class Solution {
public int numSquares(int n) {
}
}
1, 4, 9, …:
best(n) = 1 + min best(n - k²). Number theory then caps the answer at 4
(Lagrange), and tells exactly when it is 1, 2, 3 or 4 — no table needed.Instinct Choose items to hit or stay under a target sum (can it be done, best value, fewest items, how many ways) - index a DP array by the remaining capacity.
Memory hack Once? Walk back. Many? Walk forward. Each item used at most once loops capacity downward; reusable items loop it upward.
Open the Knapsack DP guide →Approaches
Brute ForcePlain Recursion over the Last Square
O(√nn) worst caseSpace O(n)Pick which square k² to use first, solve the remainder
n - k² recursively, and keep the minimum. It explores every way of
writing n as a sum of squares, recomputing the same remainders many
times.
public int numSquares(int n) { if (n == 0) return 0; int best = Integer.MAX_VALUE; for (int k = 1; k * k <= n; k++) { best = Math.min(best, 1 + numSquares(n - k * k)); } return best; }
Correct, but exponential — hopeless well before n = 104.
BetterBottom-Up DP (Unbounded Knapsack)
O(n √n)Space O(n)The recursion only touches values 0..n, so solve each once —
memoize it, or equivalently fill dp[i] from small to large. Each
dp[i] tries every square ≤ i: at most
√n options.
public int numSquares(int n) { int[] dp = new int[n + 1]; // dp[i] = fewest squares summing to i for (int i = 1; i <= n; i++) { dp[i] = i; // worst case: 1 + 1 + ... + 1 for (int k = 1; k * k <= i; k++) { dp[i] = Math.min(dp[i], dp[i - k * k] + 1); } } return dp[n]; }
Dry runn = 12
- base0········n = 8
- i=1..30123·····only 1² fits
- i=401231i····dp[0]+1 = 1
- i=5..701231234·dp[i-4]+1
- i=8012312342idp[4]+1 = 2 ✔
The expected DP answer; about 106 steps for n = 104.
OptimalNumber Theory (Four-Square Theorem)
O(√n)Space O(1)Every positive integer is a sum of at most four squares, and exactly those of
form 4a(8b+7) need four (Legendre). So: answer 1 if
n is a square, 4 if it has that form, 2 if n - k² is a
square for some k, otherwise 3.
public int numSquares(int n) { if (isSquare(n)) return 1; int m = n; while (m % 4 == 0) m /= 4; // strip factors of 4 if (m % 8 == 7) return 4; for (int k = 1; k * k < n; k++) { if (isSquare(n - k * k)) return 2; } return 3; } private boolean isSquare(int x) { int r = (int) Math.sqrt(x); return r * r == x; }
Fastest by far, but relies on theorems you must state, not derive.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion over the Last Square | O(√nn) worst case | O(n) |
| Better | Bottom-Up DP (Unbounded Knapsack) | O(n √n) | O(n) |
| Optimal | Number Theory (Four-Square Theorem) | O(√n) | O(1) |
- Greedily taking the largest square: 12 = 9+1+1+1 (4) but 4+4+4 is 3.
- Initialising
dp[i]to 0 instead of a large value (ori). - Using floating
sqrtwithout checkingr*r == xexactly.
- Say “this is coin change where coins are squares” to frame the DP instantly.
- BFS from
nby subtracting squares also works and stops at the first level reached. - If you mention Lagrange, be ready to explain the
4a(8b+7)rule.