Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution

public class Solution {
     public int numSquares(int n) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 1);
        map.put(2, 2);
        map.put(3, 3);
        map.put(4, 1);

        int result = helper(n, map);
        return result;
    }

    public int helper(int n, Map<Integer, Integer> map) {
        int sqrt = (int) Math.sqrt(n);
        if (n == sqrt * sqrt) {
            map.put(n, 1);
            return 1;
        }

        if (map.containsKey(n)) {
            return map.get(n);
        }

        int max = (int) Math.sqrt(n);

        int result = Integer.MAX_VALUE;
        for (int i = max; i >= 1; i--) {
            int candidate = helper(n - (int) Math.pow(i, 2), map) + 1;
            result = result > candidate ? candidate : result;
        }

        map.put(n, result);

        return result;
    }
}