keetcoder

# 279. Perfect Squares

LeetCode Problem Link (opens new window)

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which 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.

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^4

# Solution

Initially, this problem might not seem to provide much insight, but translating it reveals a classic dynamic programming problem.

You might translate the problem statement into a question about the "least number of items" needed to "fill a knapsack" with "perfect squares as items" that can be reused indefinitely.

Let's break down the dynamic programming approach in five steps:

  1. Determine the dp array and its meaning:

dp[j]: The minimum number of perfect squares required to sum to j.

  1. Determine the recurrence relation:

Since dp[j] can be derived from dp[j - i * i], where i * i is a perfect square, the update can be dp[j] = min(dp[j - i * i] + 1, dp[j]).

  1. Initialize the dp array:

dp[0] = 0 indicates that zero numbers are needed to sum to zero.

For other indices j, initialize dp[j] to a maximum value to ensure it gets overwritten with the correct minimal value during calculations.

  1. Determine the traversal order:

In a complete knapsack problem, if calculating the number of combinations, iterate over items first. If calculating the number of permutations, iterate over the knapsack first.

In this problem, since we seek the minimum count, it doesn't matter much, but let's start by iterating the knapsack first:

vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; i++) { // Iterate over the knapsack
    for (int j = 1; j * j <= i; j++) { // Iterate over items
        dp[i] = min(dp[i - j * j] + 1, dp[i]);
    }
}
1
2
3
4
5
6
7
  1. Example to drive the dp array:

Given an input n = 5, the dp state table will look like:

279.Perfect Squares

The final result is dp[n].

Here is the C++ solution after applying the above dynamic programming approach:

// Version 1
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) { // Traverse the knapsack
            for (int j = 1; j * j <= i; j++) { // Traverse items
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • Time Complexity: O(n * √n)
  • Space Complexity: O(n)

We can also iterate over items first, followed by the knapsack, which is also acceptable:

// Version 2
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) { // Traverse items
            for (int j = i * i; j <= n; j++) { // Traverse knapsack
                dp[j] = min(dp[j - i * i] + 1, dp[j]);
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • Same as above

# Summary

If you've diligently worked on the 0322.Coin Change (opens new window) problem, this one should feel quite straightforward as it's a similar pattern.

However, if you're approaching dynamic programming or knapsack problems without a structured approach like presented in "Code With Carl," you might find this challenging.

Below are implementations in other languages.

# Java:

class Solution {
    // Version 1, Iterating over items first
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        // Initialization
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        // When the sum is 0, the combination count is 0
        dp[0] = 0;
        // Traverse items
        for (int i = 1; i * i <= n; i++) {
            // Traverse knapsack
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}

class Solution {
    // Version 2, Iterating over knapsack first
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        // Initialization
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        // When the sum is 0, the combination count is 0
        dp[0] = 0;
        // Traverse knapsack
        for (int j = 1; j <= n; j++) {
            // Traverse items
            for (int i = 1; i * i <= j; i++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# Python:

Iterating over the knapsack first, then the items:

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):  # Traverse the knapsack
            for j in range(1, int(i ** 0.5) + 1):  # Traverse items
                dp[i] = min(dp[i], dp[i - j * j] + 1)

        return dp[n]
1
2
3
4
5
6
7
8
9
10

Iterating over the items first, then the knapsack:

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for i in range(1, int(n ** 0.5) + 1):  # Traverse items
            for j in range(i * i, n + 1):  # Traverse knapsack
                dp[j] = min(dp[j - i * i] + 1, dp[j])

        return dp[n]
1
2
3
4
5
6
7
8
9
10

# Go:

// Version 1: Iterate over items first, then knapsack
func numSquares1(n int) int {
    dp := make([]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0
    for i := 1; i * i <= n; i++ { // Iterate over items
        for j := i * i; j <= n; j++ { // Iterate over knapsack
            dp[j] = min(dp[j], dp[j-i*i]+1)
        }
    }
    return dp[n]
}

// Version 2: Iterate over knapsack first, then items
func numSquares2(n int) int {
    dp := make([]int, n+1)
    for i := 0; i <= n; i++ {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0
    for j := 1; j <= n; j++ { // Iterate over knapsack
        for i := 1; i * i <= j; i++ { // Iterate over items
            dp[j] = min(dp[j], dp[j-i*i]+1)
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# JavaScript:

// Iterate over items first, then knapsack
var numSquares1 = function(n) {
    let dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

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

// Iterate over knapsack first, then items
var numSquares2 = function(n) {
    let dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

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

    return dp[n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# TypeScript:

// Iterate over items first
function numSquares(n: number): number {
    const goodsNum: number = Math.floor(Math.sqrt(n));
    const dp: number[] = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= goodsNum; i++) {
        const tempVal: number = i * i;
        for (let j = tempVal; j <= n; j++) {
            dp[j] = Math.min(dp[j], dp[j - tempVal] + 1);
        }
    }
    return dp[n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
// Iterate over knapsack first
function numSquares(n: number): number {
  const dp = Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for(let i = 1; i <= n; i++){
      for(let j = 1; j * j <= i; j++){
          dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
      }
  }
  return dp[n];
};
1
2
3
4
5
6
7
8
9
10
11

# C:

#define min(a, b) ((a) > (b) ? (b) : (a))

int numSquares(int n) {
    int* dp = (int*)malloc(sizeof(int) * (n + 1));
    for (int j = 0; j < n + 1; j++) {
        dp[j] = INT_MAX;
    }
    dp[0] = 0;
    for (int i = 0; i <= n; ++i) { // Iterate over knapsack
        for (int j = 1; j * j <= i; ++j) { // Iterate over items
            dp[i] = min(dp[i - j * j] + 1, dp[i]);
        }
    }
    return dp[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Rust:

// Iterate over knapsack
impl Solution {
    pub fn num_squares(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![i32::MAX; n + 1];
        dp[0] = 0;
        for i in 0..=n {
            let mut j = 1;
            loop {
                match j * j > i {
                    true => break,
                    false => dp[i] = dp[i].min(dp[i - j * j] + 1),
                }
                j += 1;
            }
        }
        dp[n]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Iterate over items
impl Solution {
    pub fn num_squares(n: i32) -> i32 {
        let (n, mut goods) = (n as usize, 1);
        let mut dp = vec![i32::MAX; n + 1];
        dp[0] = 0;
        loop {
            if goods * goods > n {
                break;
            }
            for j in goods * goods..=n {
                dp[j] = dp[j].min(dp[j - goods * goods] + 1);
            }
            goods += 1;
        }
        dp[n]
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Last updated:: 9/4/2025, 3:19:38 PM

← 21. Word Break →

Copyright © 2025 keetcoder