Problem Statement

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that can be expressed as x² where x is an integer.
For example, 1, 4, 9, 16, 25, 36, ... are perfect squares.

You must find the minimum number of such numbers whose sum equals n.

Example 1

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4

Example 2

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9

Constraints

• 1 ≤ n ≤ 10⁴

---

Intuition and Approach

We are asked to find the minimum count of perfect squares that sum up to n.
At first glance, this might remind you of the Coin Change Problem, where coins are replaced by perfect squares.

Naive Approach – Recursion (Exponential Time)

One could recursively try all combinations of perfect squares ≤ n and pick the combination with the fewest terms. However, this becomes exponential in time complexity, since the same subproblems (for smaller numbers) are solved repeatedly.

Example:

n = 12
Try 1² → remaining 11
Try 2² → remaining 8
Try 3² → remaining 3

Each branch further tries 1², 2², 3², etc., leading to massive overlap. Hence, we move to Dynamic Programming (DP).

---

Dynamic Programming Approach (Bottom-Up)

We use an array dp[i] to store the minimum number of perfect squares required to sum up to i.

Step-by-Step Explanation

1. Initialization
   • dp[0] = 0 since zero requires no numbers.
   • For all other values, initialize dp[i] = ∞ (or a large number).
2. Transition
   • For each number i from 1 to n,
     check all perfect squares j*j ≤ i.
     Then we use: dp[i] = min(dp[i], dp[i - j*j] + 1) The +1 represents using the perfect square j*j.
3. Return Value
   • Finally, dp[n] contains the minimum number of perfect squares that sum up to n.

---

Example Dry Run

Let’s compute for n = 12:

Perfect squares ≤ 12 → [1, 4, 9]

We build dp step by step:

i	Perfect Square Options	dp[i] Calculation	Result
0	–	0	0
1	1²=1 → dp[1-1]+1=1	1
2	1²=1 → dp[1]+1=2	2
3	1²=1 → dp[2]+1=3	3
4	1²=1 → dp[3]+1=4, 2²=4 → dp[0]+1=1	1
5	1²=1 → dp[4]+1=2, 2²=4 → dp[1]+1=2	2
6	1²=1 → dp[5]+1=3, 2²=4 → dp[2]+1=3	3
7	1²=1 → dp[6]+1=4, 2²=4 → dp[3]+1=4	4
8	1²=1 → dp[7]+1=5, 2²=4 → dp[4]+1=2	2
9	1²=1 → dp[8]+1=3, 2²=4 → dp[5]+1=3, 3²=9 → dp[0]+1=1	1
10	1², 2², 3² → min(dp[9]+1=2, dp[6]+1=4, dp[1]+1=2)	2
11	1², 2², 3² → min(dp[10]+1=3, dp[7]+1=5, dp[2]+1=3)	3
12	1², 2², 3² → min(dp[11]+1=4, dp[8]+1=3, dp[3]+1=4)	3

So dp[12] = 3 → 4 + 4 + 4

---

Java Implementation

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

---

Explanation of Code

• dp[i - j*j] + 1 means: if we already know how many squares sum to (i - j²), then adding one more square (j²) gives us a possible way to form i.
• Math.min() ensures we always keep the minimal count.
• The outer loop (i) iterates up to n, and inner loop (j) iterates up to √n, giving O(n√n) complexity.

---

Complexity Analysis

• Time Complexity: O(n * √n)
  For each i, we test all squares ≤ i, i.e., up to √i.
• Space Complexity: O(n)
  Only the dp array of size n + 1 is used.

---

Alternate Approaches

1. Breadth-First Search (BFS)

• Treat each number as a node in a graph.
• Each edge represents subtracting a perfect square.
• Start from n and perform BFS until reaching 0.
• The depth of the BFS tree when 0 is reached equals the answer.

This approach is elegant and avoids recomputation but has similar time complexity to DP.

2. Mathematical Solution (Number Theory)

Using Lagrange’s Four Square Theorem:

Every positive integer can be expressed as the sum of four or fewer perfect squares.

This means the answer will always be 1, 2, 3, or 4.

We can test conditions:

• If n is a perfect square → 1
• If n = a² + b² → 2
• If n can be expressed as 4^k(8m + 7) → 4 (special case)
• Else → 3

This mathematical shortcut is very fast (O(√n)), but more complex to code.

---

BFS Java Implementation (for completeness)

public int numSquaresBFS(int n) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[n + 1];
    queue.add(n);
    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        level++;
        for (int i = 0; i < size; i++) {
            int curr = queue.poll();
            for (int j = 1; j * j <= curr; j++) {
                int next = curr - j * j;
                if (next == 0) return level;
                if (!visited[next]) {
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
    return level;
}

---

Comparison of Methods

Method	Time Complexity	Space Complexity	Pros	Cons
DP	O(n√n)	O(n)	Simple, iterative	Slightly slower for large n
BFS	O(n√n)	O(n)	Conceptually clean, shortest path view	Slightly more memory
Math (Lagrange)	O(√n)	O(1)	Fastest	Harder to understand / implement

---

Key Takeaways

1. The DP approach is most intuitive and suitable for interviews.
2. Always build dp bottom-up; it guarantees optimal substructure.
3. The BFS and mathematical methods show interesting alternative perspectives on the same problem.
4. This problem is an example of Dynamic Programming + Number Theory synergy.