Perfect squares

Math Dynamic Programming Breadth-First Search

56.3% acceptance

Jan 12, 2026

11801

492

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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 1..=n {
      let mut j = 1;
      while j * j <= i {
        dp[i] = dp[i].min(dp[i - j * j] + 1);
        j += 1;
      }
    }
    
    dp[n]
  }
}