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

Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:

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

Mathematically proven that we need at most up to 4 perfect squares that can be sum up to any positive integers. We also known in this post that we can use Dynamic programming to compute the least number of perfect square numbers that sum up to n.

The DP equation is:

1
2

f(0) = 0
f(i) = min(f(i), f(i - j * j); // for j * j <= i

f(0) = 0
f(i) = min(f(i), f(i - j * j); // for j * j <= i

To print which perfect square numbers are summing up to N, we can use another array to record the last perfect square and then keep tracking back last perfect squares until nothing remained. This works because of the inherent Dynamic Programming characteristics – the sub problems are also optimial.

The following Python solution prints the solution to the least number of perfect square sums, for example: 1234 = sqr(3) + sqr(35).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def computeMinSquare(N):
    M = 100000 # marks as not-visited
    ans = [M] * (N+1)
    last = [0]* (N+1)
    ans[0] = -1
    for i in range(1, N+1):    
        for j in range(i):
            if (i >= j * j) and ans[i - j*j] != M and (ans[i] > ans[i-j*j]+1):
                last[i] = j  # remember the perfect square
                ans[i] = min(ans[i], ans[i - j * j] + 1) # DP Equation
    s = []
    j = N
    while (j > 0) and (last[j] > 0):
        a = last[j]
        s.append("sqr("+str(a) + ")")
        j = j - last[j]*last[j]
    print(str(N) + " = " + " + ".join(s))
 
# prints 1234 = sqr(3) + sqr(35)
computeMinSquare(1234)

def computeMinSquare(N):
    M = 100000 # marks as not-visited
    ans = [M] * (N+1)
    last = [0]* (N+1)
    ans[0] = -1
    for i in range(1, N+1):    
        for j in range(i):
            if (i >= j * j) and ans[i - j*j] != M and (ans[i] > ans[i-j*j]+1):
                last[i] = j  # remember the perfect square
                ans[i] = min(ans[i], ans[i - j * j] + 1) # DP Equation
    s = []
    j = N
    while (j > 0) and (last[j] > 0):
        a = last[j]
        s.append("sqr("+str(a) + ")")
        j = j - last[j]*last[j]
    print(str(N) + " = " + " + ".join(s))

# prints 1234 = sqr(3) + sqr(35)
computeMinSquare(1234)

–EOF (The Ultimate Computing & Technology Blog) —