Problem Description

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

You may use each perfect square number as many times as needed. Your goal is to minimize the count of perfect squares that sum up exactly to n.

Key constraints:

• 1 ≤ n ≤ 10,000
• There is always at least one valid solution for every n
• You can reuse the same perfect square multiple times

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

Thought Process

At first glance, this problem seems similar to the classic coin change problem. For each number from 1 up to n, we want to find the minimal number of perfect squares that sum to that number.

A brute-force approach would try all combinations of perfect squares less than or equal to n, recursively subtracting them from n until reaching zero, and keeping track of the minimum count. However, this quickly becomes inefficient for larger values of n due to repeated calculations.

To optimize, we should avoid recalculating the minimal count for the same value multiple times. This suggests using dynamic programming (DP) or breadth-first search (BFS) to build up the answer efficiently.

The analogy is: imagine you have coins of denominations equal to all perfect squares ≤ n, and you want to make change for n with the fewest coins.

Solution Approach

We'll use a dynamic programming approach to solve the problem efficiently. Here’s how we can break it down:

1. Generate all perfect squares ≤ n:
   • Compute all numbers i such that i * i ≤ n and store them in a list.
2. Initialize a DP array:
   • Create an array dp of size n + 1, where dp[i] represents the least number of perfect squares that sum to i.
   • Set dp[0] = 0 (zero can be formed with zero numbers), and initialize the rest with infinity (or a large number).
3. Fill the DP array:
   • For each number from 1 to n:
   • For each perfect square less than or equal to the current number, update dp[i] as:
   • dp[i] = min(dp[i], dp[i - square] + 1)
4. Final answer:
   • The answer is dp[n], which gives the minimum number of perfect squares that sum to n.

This method ensures that each subproblem is solved only once, and the solution for each value is built upon smaller values.

Example Walkthrough

Let's walk through the algorithm for n = 12:

1. Perfect squares ≤ 12: [1, 4, 9]
2. Initialize dp: dp[0] = 0, dp[1..12] = ∞
3. Fill dp step by step:
   • dp[1] = min(dp[1 - 1] + 1) = dp[0] + 1 = 1
   • dp[2] = min(dp[2 - 1] + 1) = dp[1] + 1 = 2
   • dp[3] = min(dp[3 - 1] + 1) = dp[2] + 1 = 3
   • dp[4] = min(dp[4 - 1] + 1, dp[4 - 4] + 1) = min(dp[3] + 1, dp[0] + 1) = min(4, 1) = 1
   • Continue this up to dp[12]...
   • dp[12] = min(dp[12 - 1] + 1, dp[12 - 4] + 1, dp[12 - 9] + 1) = min(dp[11] + 1, dp[8] + 1, dp[3] + 1) = min(4, 2, 4) = 3
4. Result: dp[12] = 3 (as 12 = 4 + 4 + 4)

Time and Space Complexity

Brute-force approach:

• Highly inefficient; explores all combinations recursively.
• Time complexity: Exponential in n (since each call branches into all possible perfect squares).
• Space complexity: Proportional to the recursion depth (up to n).

• Time complexity: O(n * sqrt(n))
• Explanation: For each i from 1 to n, we loop through all perfect squares ≤ i (at most sqrt(n) per i).
• Space complexity: O(n) for the DP array.

Summary

To solve the "Perfect Squares" problem, we use dynamic programming to efficiently compute the minimum number of perfect squares that sum to a given n. By breaking the problem into subproblems and reusing solutions, we avoid redundant calculations and achieve a solution that scales well even for large n. The approach is elegant because it builds up the answer in a bottom-up fashion, similar to the coin change problem, making it both intuitive and efficient.

Code Implementation

import math

class Solution:
    def numSquares(self, n: int) -> int:
        # Generate all perfect squares ≤ n
        squares = [i * i for i in range(1, int(math.isqrt(n)) + 1)]
        
        # Initialize DP array
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(1, n + 1):
            for square in squares:
                if square > i:
                    break
                dp[i] = min(dp[i], dp[i - square] + 1)
        return dp[n]
      

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        vector<int> squares;
        for (int i = 1; i * i <= n; ++i) {
            squares.push_back(i * i);
        }
        for (int i = 1; i <= n; ++i) {
            for (int square : squares) {
                if (square > i) break;
                dp[i] = min(dp[i], dp[i - square] + 1);
            }
        }
        return dp[n];
    }
};
      

import java.util.*;

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        ArrayList<Integer> squares = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            squares.add(i * i);
        }
        for (int i = 1; i <= n; i++) {
            for (int square : squares) {
                if (square > i) break;
                dp[i] = Math.min(dp[i], dp[i - square] + 1);
            }
        }
        return dp[n];
    }
}
      

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    let squares = [];
    for (let i = 1; i * i <= n; i++) {
        squares.push(i * i);
    }
    let dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let square of squares) {
            if (square > i) break;
            dp[i] = Math.min(dp[i], dp[i - square] + 1);
        }
    }
    return dp[n];
};