Teaching Kids Programming: Videos on Data Structures and Algorithms
This article explores an iterative-deepening recursive solution to LeetCode 279, Perfect Squares. By combining depth-limited search with Lagrange’s Four Square Theorem, we only need to test whether a number can be represented using one, two, or three perfect squares—otherwise, the answer must be four. The approach is also compared with dynamic programming, BFS, and a pure number-theory solution.
Minimum Number of Perfect Squares via Iterative Deepening DFS
Finding the Minimum Number of Perfect Squares with Iterative Deepening DFS
Perfect Squares: A Theorem-Guided Iterative Deepening Search
LeetCode 279: Perfect Squares via Depth-Limited Recursive Search
LeetCode 279: Perfect Squares
Given a positive integer n, the problem asks us to find the minimum number of perfect squares whose sum equals n.
For example:
12 = 4 + 4 + 4, so the answer is3.13 = 4 + 9, so the answer is2.16is already a perfect square, so the answer is1.
The standard solutions include dynamic programming and breadth-first search. However, there is also a surprisingly compact approach based on depth-limited search and Lagrange’s Four Square Theorem.
The Theorem-Guided Recursive Approach
Here is the solution:
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
sqrs = [i * i for i in range(1, isqrt(n) + 1)]
def f(cur, i):
if i == 1:
return cur in sqrs
for x in sqrs:
if f(cur - x, i - 1):
return True
return False
for i in range(1, 4):
if f(n, i):
return i
return 4
The solution is short, but several important ideas are packed into it.
Generating the Perfect Squares
The first line generates every positive perfect square that is no greater than n:
sqrs = [i * i for i in range(1, isqrt(n) + 1)]
For example, if n = 13, then:
sqrs = [1, 4, 9]
The largest possible square we need is:
isqrt(n) * isqrt(n)
Python’s isqrt() returns the exact integer square root without using floating-point arithmetic. It is generally preferable to writing:
int(n ** 0.5)
For small values of n, both work. However, isqrt() is explicit and avoids floating-point precision problems for larger integers.
What Does f(cur, i) Mean?
The recursive function answers a yes-or-no question:
Can cur be represented as the sum of exactly i positive perfect squares?
For example:
f(13, 1)asks whether 13 itself is a perfect square.f(13, 2)asks whether 13 can be written as the sum of two squares.f(12, 3)asks whether 12 can be written as the sum of three squares.
When only one square remains to be selected, the problem becomes a simple membership test:
if i == 1:
return cur in sqrs
If cur is a perfect square, the required representation has been found.
Otherwise, the function chooses one square, subtracts it from the current value, and recursively tries to construct the remainder using one fewer square:
for x in sqrs:
if f(cur - x, i - 1):
return True
The same square may be selected more than once because every recursive call starts iterating from the beginning of sqrs. This is necessary for representations such as:
12 = 4 + 4 + 4
Why Check Only One, Two, and Three Squares?
The outer loop tests the possible answers in increasing order:
for i in range(1, 4):
if f(n, i):
return i
Notice that range(1, 4) produces only:
1, 2, 3
The algorithm does not search for a representation using four squares. It simply returns 4 if the first three searches fail.
This is justified by Lagrange’s Four Square Theorem:
Every positive integer can be represented as the sum of at most four integer squares.
Therefore, the answer to this problem can only be 1, 2, 3, or 4.
Because the algorithm checks the answers in increasing order, the first successful search must also be the minimum answer. If none of 1, 2, and 3 works, the answer must be 4.
This theorem is not merely a small optimization. It is the reason the recursive search has a constant maximum depth.
Example: n = 13
The algorithm first evaluates:
f(13, 1)
Since 13 is not in [1, 4, 9], the result is false.
It then evaluates:
f(13, 2)
Suppose the loop selects 4. The recursive call becomes:
f(13 - 4, 1)
f(9, 1)
Since 9 is a perfect square, the function returns true. Therefore:
13 = 4 + 9
The final answer is 2.
Example: n = 12
The one-square search fails because 12 is not a perfect square.
The two-square search also fails because 12 cannot be represented as the sum of two perfect squares.
During the three-square search, the recursion can find:
12 - 4 = 8
8 - 4 = 4
The remaining value, 4, is a perfect square. Therefore:
12 = 4 + 4 + 4
The answer is 3.
A Performance Detail: sqrs Is a List
The expression below performs a linear search because sqrs is a list:
cur in sqrs
Let m = floor(sqrt(n)). There are m squares in the list.
For a three-square search, the recursion may choose two squares before reaching the membership test. In the worst case, that gives approximately:
m * m * m
operations. The worst-case time complexity of the code as written is therefore:
O(m³) = O(n^(3/2))
The recursion depth is never more than three, so stack usage is constant. The square list requires O(sqrt(n)) space.
For the problem’s relatively small constraint, this compact implementation can still be practical. However, using a set makes the membership test constant-time on average.
An Improved Version
We can retain the same idea while adding a set for lookup and stopping when the selected square is already too large:
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
squares = [i * i for i in range(1, isqrt(n) + 1)]
square_set = set(squares)
def can_sum(cur, count):
if count == 1:
return cur in square_set
# The remaining count - 1 squares are each at least 1.
limit = cur - (count - 1)
for square in squares:
if square > limit:
break
if can_sum(cur - square, count - 1):
return True
return False
for count in range(1, 4):
if can_sum(n, count):
return count
return 4
The recursion still performs a depth-limited search, but the final perfect-square lookup is now O(1) on average.
For the three-square case, at most two nested square choices are explored. Its worst-case time complexity becomes approximately:
O(m²) = O(n)
The pruning condition also prevents the recursion from exploring branches that cannot possibly contain enough positive squares.
Dynamic Programming
The most common general-purpose solution uses dynamic programming.
Define dp[x] as the minimum number of perfect squares required to sum to x. If the last selected square is s, then:
dp[x] = min(dp[x], dp[x - s] + 1)
The complete implementation is:
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
squares = [i * i for i in range(1, isqrt(n) + 1)]
dp = [0] + [float("inf")] * n
for value in range(1, n + 1):
for square in squares:
if square > value:
break
dp[value] = min(
dp[value],
dp[value - square] + 1
)
return dp[n]
For n = 12, some of the states are:
dp[1] = 1, using1.dp[4] = 1, using4.dp[8] = 2, using4 + 4.dp[12] = 3, using4 + 4 + 4.
There are n states, and each state considers up to sqrt(n) squares.
The complexity is:
- Time:
O(n sqrt(n)) - Space:
O(n)
Dynamic programming does not depend on the Four Square Theorem for its correctness. It is also easier to adapt to related minimum-coin and minimum-composition problems.
Breadth-First Search
The problem can also be interpreted as an unweighted shortest-path problem.
Treat each remaining value as a graph node. From a value x, we can subtract any perfect square that is no greater than x.
For example, from 13 we can reach:
13 - 1 = 12
13 - 4 = 9
13 - 9 = 4
Each edge represents selecting one perfect square. Therefore, the shortest distance from n to zero is the minimum number of squares.
from collections import deque
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
squares = [i * i for i in range(1, isqrt(n) + 1)]
queue = deque([(n, 0)])
seen = {n}
while queue:
remaining, depth = queue.popleft()
for square in squares:
if square > remaining:
break
next_remaining = remaining - square
if next_remaining == 0:
return depth + 1
if next_remaining not in seen:
seen.add(next_remaining)
queue.append((next_remaining, depth + 1))
BFS explores all representations using one square before exploring representations using two squares, then three squares, and so on. The first time it reaches zero, it has found the minimum answer.
Its worst-case complexity is:
- Time:
O(n sqrt(n)) - Space:
O(n)
Conceptually, BFS and dynamic programming solve the same state-transition problem. DP fills the states numerically, while BFS explores them in increasing distance from the starting value.
A Pure Number-Theory Solution
We can go further and avoid DP, BFS, and recursive enumeration almost entirely.
The solution combines two mathematical results:
- Lagrange’s Four Square Theorem guarantees that the answer is at most four.
- Legendre’s Three Square Theorem identifies exactly when an integer cannot be represented using three squares.
Legendre’s theorem says that a positive integer cannot be represented as the sum of three integer squares precisely when it has the form:
4^a * (8b + 7)
This gives the following implementation:
from math import isqrt
class Solution:
def numSquares(self, n: int) -> int:
def is_square(value):
root = isqrt(value)
return root * root == value
if is_square(n):
return 1
for a in range(1, isqrt(n) + 1):
if is_square(n - a * a):
return 2
reduced = n
while reduced % 4 == 0:
reduced //= 4
if reduced % 8 == 7:
return 4
return 3
The logic is:
- If
nis a square, return1. - If
n - a²is a square for somea, return2. - If the reduced number is congruent to 7 modulo 8, return
4. - Otherwise, after excluding answers 1 and 2, the answer must be
3.
This approach runs in O(sqrt(n)) time and uses O(1) additional space. It is asymptotically the fastest solution, although it depends on mathematical theorems that do not generalize to ordinary coin-change problems.
Comparison of the Approaches
| Approach | Time Complexity | Space Complexity | Main Advantage |
|---|---|---|---|
| Original depth-limited DFS | O(n^(3/2)) |
O(sqrt(n)) |
Very compact and directly uses the four-square bound |
| DFS with set lookup | O(n) |
O(sqrt(n)) |
Preserves the elegant recursive structure |
| Dynamic programming | O(n sqrt(n)) |
O(n) |
General and easy to adapt |
| Breadth-first search | O(n sqrt(n)) |
O(n) |
Natural shortest-path interpretation |
| Number theory | O(sqrt(n)) |
O(1) |
Best theoretical complexity |
Final Thoughts
The recursive solution is interesting because it combines brute-force search with a strong mathematical bound. Without Lagrange’s Four Square Theorem, returning 4 after checking only three cases would be unjustified. With the theorem, the recursion never needs to go deeper than three levels.
The code is therefore better described as a theorem-guided, depth-limited search rather than unrestricted brute force.
The original implementation is already concise and readable. Its main performance weakness is that cur in sqrs performs a linear list search. Adding a set reduces the perfect-square test to constant time on average and lowers the worst-case search complexity substantially.
For this specific problem, the number-theory solution is the fastest. For learning reusable algorithmic patterns, however, dynamic programming and BFS are more valuable. The depth-limited recursive solution sits nicely between them: it is compact, intuitive, and demonstrates how mathematical knowledge can dramatically reduce a search space.
Day 107 on Perfect Squares using Dynamic Programming (Recursive Depth First Search Algorithm Cached)? Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Least Number of Perfect Squares
- Teaching Kids Programming – Minimum Number of Perfect Squares via Theorem-guided iterative deepening DFS
Teaching Kids Programming: Videos on Data Structures and Algorithms This article explores an iterative-deepening recursive solution to LeetCode 279, Perfect… - Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Least Number of Perfect Squares
Teaching Kids Programming: Videos on Data Structures and Algorithms Given an integer n, return the least number of perfect square… - Find the Least Number Sums of Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …)… - Dynamic Programming – Perfect Squares
Find the least number of perfect square numbers (1, 4, 9, 16, 25 …) which sum to the given integer… - Teaching Kids Programming – Compute the Maximal Perimeter by Forming a Rectangle from N squares
Teaching Kids Programming: Videos on Data Structures and Algorithms Given N squares which side is M, we want to re-arrange…
–EOF (The Ultimate Computing & Technology Blog) —
2580 wordsLast Post: Hardening WordPress: Disable PHP Execution in `wp-content/uploads`