如题：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

这道题和leetcode 752. 打开转盘锁类似，都可以使用广度优先搜索来求解。大体思路都是根据遍历当前节点的子节点，寻找目标解的过程，类似题目做多了，就比较容易了。

这道题可以看作从根节点0出发，往下搜索子节点，找到匹配则返回深度即可，相当于最短路径，当然是广度优先搜索BFS。
每层节点的子节点分别为父节点加上(1, 4, 9, 16....(i^2 < n) )。使用队列存储节点，每次遍历前先获取当层节点数，即队列长度。然后依次遍历该节点子节点，如果长度符合则返回，不符合且是第一次访问，则添加到队列中去，如果已经访问过，则不需要添加。需要额外的哈希数组，用来存储访问过的元素，队列和哈希数组总共需要额外的2N的空间。bfs搜索方法协同队列的使用代码框架比较固定，往往可以共用一套代码。下面是本题的图示：

c语言代码如下，前面部分代码是关于队列实现的，可以略过不看，仅看最后的bfs搜索部分即可。

/* BFS */

typedef struct {
    int length, max;
    int front, rear;
    int *sq;
} queue;

//创建队列
queue* queueCreate(int k) {
    queue* a;
    if (k < 0)
        return NULL;
    else
        a = (queue*) malloc(sizeof(queue));
    if (!a)
        return NULL;
    else
    {
        a->max = k+1;
        a->length = a->front = a->rear = 0;
        a->sq = (int *)malloc(sizeof(int) * (k+1));
        if (!a->sq)
        {
            free(a);
            return NULL;
        }
        return a;
    }    
}

//入队列
int enQueue(queue* obj, int value) {
    if (obj->length == (obj->max - 1))
        return 0;
    else
    {
        obj->sq[obj->rear] = value;
        obj->rear = (obj->rear + 1) % obj->max;
        obj->length++;
    }
        
    return 1;
}

//出队列
int deQueue(queue* obj) {
    int head;
    
    if (obj->front == obj->rear)
        return 0;
    else
    {
        head= obj->front;
        obj->front = (obj->front + 1) % obj->max;
        obj->length--;
        return obj->sq[head];
    }
}

//获取当前队列长度
int queueLength(queue *obj)
{
    return obj->length;
}

//判断队列是否为空
int isEmpty(queue* obj) {
     if (obj->front == obj->rear)
        return 1;
    else
        return 0;
}

//判断队列是否满
int isFull(queue* obj) {
    if (obj->length == obj->max - 1)
        return 1;
    else
        return 0;
}

//释放队列
void queueFree(queue* obj) {
    free(obj->sq);
    free(obj);
    return;
}


int numSquares(int n){
    int i,j,next, curr, size, steps = 0, *visited;
    queue *q;
    
    if (n == 0 || n == 1)
        return n;
    
    q = queueCreate(n + 1);
    visited = (int *)malloc(sizeof(int) * (n+1));
    for (i = 0; i <= n; i++)
        visited[i] = 0;
    
    enQueue(q, 0);
    visited[0] = 1;
    
    while(!isEmpty(q))
    {
        //深度递增
        steps++;
        size = queueLength(q);
        for (i = 0; i < size; i++)
        {
            //遍历子节点
            curr = deQueue(q);
            for (j = 1; j * j <= n; j++)
            {
                next = curr + j*j;
                if (next == n) return steps;
                if (next > n) break;
                if (visited[next]) continue;
                //加入到队列，以待访问其子节点
                visited[next] = 1;
                enQueue(q, next);
            }
        }
    }
    queueFree(q);
    free(visited);
    return steps;
}