title: Find minimum no. of perfect squares that sums to n using BFS algo
body: <p>We are given an integer n, we have to determine the least no. of perfect squares which sum to n.</p>
  <p>Example :</p>
  <pre><code>n = 12
  and perfect squares up to n are 1, 4, 9, 16, 25... up to n
  in this case these will be 1, 4, 9
  so output will be 3 as 12 = 4 + 4 + 4
  </code></pre>
  <p>This is code in C++ which implements BFS.</p>
  <pre class="lang-cpp prettyprint-override"><code>int numSquares(int n) {
      if(n &lt; 0) return -1;
      if(n == 1) return 1;
      vector&lt;int&gt; perfectSqs;
      queue&lt;int&gt; q;
      int level = 0;
      // for(int i=1; i*i&lt;=n; i++) {
      //     perfectSqs.push_back(i*i);
      // }
      // for(int i=0; i&lt;perfectSqs.size(); i++) {
      //     cout&lt;&lt;perfectSqs[i]&lt;&lt;' ';
      // }
      q.push(n);
      while(!q.empty()) {
          int size = q.size();
          for(int i=0; i&lt;size; i++) {
              int curr = q.front();
              q.pop();
              if(curr == 0) return level;
              for(int j=1; j*j&lt;=curr; j++) {
                  int next = curr - j*j;
                  q.push(next);
              }
          }
          level++;
      }
      return -1;
  </code></pre>
  <p>Everything else runs absolutely fine but time exceeds for input <code>7168</code>. <code>7167</code> also runs.</p>
  <p>Can someone let me know where I am wrong?</p>