279. Perfect Squares

class Solution {
    Set<Integer> squared = new HashSet<Integer>();
    Set<Integer> nums = new TreeSet<Integer>();
    int l = Integer.MAX_VALUE;
    public int numSquares(int n) {
        int root = (int) Math.sqrt(n);
        
        for (int i = 1; i <= root; i++) {
            squared.add(i * i);
        }
        
        l = Integer.MAX_VALUE;
        
        backtrack(n, 0);
        
        return l;
    }
    
    public void backtrack(int num, int level) {
        if (squared.contains(num)) {
            if (level + 1 < l) l = level + 1;
        } else {
            for (Integer s : squared) {
                if (s < num) {
                    backtrack(num - s, level + 1);
                } else {
                    break;
                }
            }
        }
    }
}

Wrong Answer..
117 / 588 test cases passed.

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j * j <= i; j++){
                dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
            }
        }
        return dp[n];
    }
}

Runtime: 32 ms, faster than 71.04% of Java online submissions for Perfect Squares.
Memory Usage: 37.8 MB, less than 88.98% of Java online submissions for Perfect Squares.

자신감을 이 문제 하나로 다 박살냈네요^^
이거 다른 solutions도 전씨와 함께 탐구하고 싶읍니다^^