Concise BFS Solution in 20 Lines

  • 0

    Let's make 0 as the root of the tree, the children of the 0 root can be generated as 1^2,2^2,3^2,...,m^2 where m=sqrt(n). Then, the children of the child node 1^2 can be generated as 1^2+1^2,1^2+2^2,..., and the children of 2^2 can be generated as 2^2+1^2,2^2+2^2,.... We apply BFS on the tree to find the first node which equals to the target n. The depth of this node is the least number of perfect square numbers which sum to n.

    int numSquares(int n) {
        int m = sqrt(n);
        queue<pair<int,int>> q;
        q.push({0, 0});
        while (!q.empty())
            int s = q.front().first;
            int depth= q.front().second;
            for (int i = 1; i <= m; i++)
                int a = s + i * i;
                if (a < n)
                    q.push({a, depth + 1});
                if (a == n)
                    return depth + 1;
        return 0;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.