<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:
int funct(int ind,vector<int>& a,int count,int sum,int n){
    if(sum==n){
        return count;
    }
    
    if(ind==a.size()||sum>n){
        return INT_MAX;
    }
    
    
    return min(funct(ind,a,count+1,sum+a[ind],n),funct(ind+1,a,count,sum,n));
}


    int numSquares(int n) {
        vector<int> a;
      
        for(int i=1;i<=100;i++){
            a.push_back(i*i);
        }
       
queue<pair<int,int>> q;
int ans=INT_MAX;
for(int i=0;i<100;i++){
    if(a[i]==n){
        return 1;
    }
    q.push({a[i],1});
}
while(!q.empty()){
    int number=q.front().first;
    int steps=q.front().second;
    q.pop();
    for(int i=0;i<100;i++){
        int newno=number+a[i];
        int newsteps=steps+1;
        if(newno>n){
            continue;
        }
        else if(newno==n){
            ans=newsteps;
            break;
        }
        else{
            q.push({newno,newsteps});
        }
    }
    if(ans!=INT_MAX){
        break;
    }

}

        return ans;
    }
};
97054