DSA problem
Perfect Squares
Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Conceptually this is a Coin Change variant where the "coins" are the infinite supply of perfect squares 1, 4, 9, 16, ... up to n, and we want the minimum count of squares that sum to n. Since each square may be reused without limit, this fits the unbounded-knapsack minimization template exactly.
Define dp[i] as the minimum number of perfect squares summing to i. The base case is dp[0] = 0 because zero squares are needed to make zero. For every i from 1 to n, we try every j such that j * j <= i and relax dp[i] = min(dp[i], dp[i - j * j] + 1). We start dp[i] from a safe upper bound (such as i, since i ones always work), so the minimum is well-defined.
The complexity is O(n * sqrt(n)) time and O(n) space — for each of the n amounts we try roughly sqrt(n) squares. By Lagrange's four-square theorem the answer is always 1, 2, 3, or 4, but the DP approach is still the cleanest production solution and generalizes directly to other unbounded-knapsack problems.
Examples
n = 123n = 132n = 11Constraints
- 1 <= n <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.