<p>Given an integer <code>n</code>, return <em>the least number of perfect square numbers that sum to</em> <code>n</code>.</p>

<p>A <strong>perfect square</strong> is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, <code>1</code>, <code>4</code>, <code>9</code>, and <code>16</code> are perfect squares while <code>3</code> and <code>11</code> are not.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 12
<strong>Output:</strong> 3
<strong>Explanation:</strong> 12 = 4 + 4 + 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 13
<strong>Output:</strong> 2
<strong>Explanation:</strong> 13 = 4 + 9.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    struct Node
    {
        int value;
        int numPerfectSquares; 
        int * compare; 
        std::map<int,int> * cache;

        Node():value(0),numPerfectSquares(0),compare(nullptr),cache(nullptr)
        {

        }

        Node(int v, int n, int * cmp, std::map<int,int> * cc):value(v),numPerfectSquares(n),compare(cmp),cache(cc)
        {

        }
    };

    
    void Build(const Node node,  int n) const noexcept
    {
        if(node.value<n)
        {         
            (*node.cache)[node.value] = node.numPerfectSquares;
            if((*node.cache).find(n - node.value)!=(*node.cache).end())
            {
                if(*node.compare > node.numPerfectSquares + (*node.cache)[n-node.value])
                    *node.compare = node.numPerfectSquares + (*node.cache)[n-node.value];
            }
            else
            {
                for(int i=1+std::sqrt(n-node.value);i>=1;i--)
                {
                    for(int j=4;j>=1;j--)
                    {
                        if(node.value + i*j*j <= n)
                        {
                            if(node.numPerfectSquares + j < *node.compare && node.numPerfectSquares + j <= 4)
                            {
                                
                                Node newNode = node;
                                newNode.value += i*i*j;
                                newNode.numPerfectSquares+=j;
                                Build(newNode,n);                    
                            }
                        }
                    }
                }
            }
        }
        else if(node.value == n)
        {
            if(*node.compare>node.numPerfectSquares)
                *node.compare = node.numPerfectSquares;
                
        }
        return;
    }

    const int numSquares(const int n) const noexcept {

        int compare = 10001;
        std::map<int,int> cache;
        Node root(0,0,&compare,&cache);
        Build(root,n);

        return compare;
    }
};
22028