Minimum number of perfect squares whose sum equals to given number

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

Example:

Input: n = 34
Output: 2
Explanation: 34 = 25 + 9.

Approach: We can solve it using recursive approach. The recursion will be something like:

• result = n
• WHILE a * a <= n
• result = Min (result, 1 + Fn(n - a*a))

That means we will recursively calculate for every n - x where x is every perfect square less than or equals to n and then take its minimum. It will solve our problem but the complexity will be exponential. If we look at it again we are kind of calculating same sub problems repeatedly. This tells us we can use DP here. 

We can have a Table where Table[i] tells minimum number of perfect squares whose sum equals to i. Obviously Table[n] is our answer. Here is how we can fill the table:

• Table[0...3] = {0...3}
• Table[i] = i
• Foreach j where j = 1 to j * j <= i
• Table[i] = Min(Table[i], 1 + Table[i - j *j])

That's all!

Implementation in C#:

        public static int MinNumPerfectSquares(int n)

        {

            if (n <= 3)

            {

                return n;

            }

            if (IsPerfectSquare(n))

            {

                return 1;

            }

            int[] table = new int [n + 1];

            for (int i = 0; i <= 3; ++i)

            {

                table[i] = i;

            }

            for (int i = 4; i <= n; ++i)

            {

                table[i] = i;

                for (int j = 1; j * j <= i; ++j)

                {

                    table[i] = Math.Min(table[i], 1 + table[i - j * j]);

                }

            }

            return table[n];

        }

Complexity: O(nlogn)