Least Num Of Perfect Squares

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
Given a positive integer n, 
find the least number of perfect square numbers which sum to n.
(for example, 1, 4, 9, 16, ...)

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.


Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
*/

func numSquares(n int) int {
    var perfect_squares []int
    for i:= 1; i*i<=n; i++{
        if i*i == n{
            return 1
        }
        perfect_squares = append(perfect_squares, i*i)
    }
    
    ans := 0 
    queue := []int{n}
    
    for len(queue) != 0  {
        /*
        ans 1, queue is [12] 
        ans 2, the paths are 1,4,9 -> queue becomes [11 8 3], 
        following the paths 1,4,9, the new level becomes [10 7 2 7 4 2]
        ans = 3, it returns at 4, the shortest path to 0 turns out to be 12 -> 8 -> 4 -> 0 
        */
        ans += 1
        var next_level []int
        for _, num := range(queue){
            for _, perf := range(perfect_squares){
                if num == perf{
                    return ans
                }
                if num<perf{
                    break
                }
                next_level = append(next_level, num-perf)
            } 
            
        }
        queue = next_level 
    }
    return ans 
}