279. Perfect Squares

BFS，过程见图

public int numSquares(int n) {
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> s = new HashSet<>();
    if (n > 0) q.offer(n); // n is positive
    int res = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        res++;
        for (int i = 0; i < size; i++) {
            int val = q.poll();
            if (!s.add(val)) continue;
            for (int j = 0; j * j <= val; j++) {
                if (val - j * j == 0) return res;
                q.offer(val - j * j);
            }
        }
    }
    return res; // if n == 0
}