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.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

`1 <= n <= 10`

^{4}

class Solution {
public:
int numSquares(int n) {
}
};