CS 514, Algorithms, Spring 2026
Optional HW7 (1% extra credit)
Due Monday 5/18 at 9:59pm.

Most students didn't do very well on the final DP problem in the midterm: integer partitions.

So you now have the option of redoing it for 1% extra credit.
It's totally optional though.

You only need to submit partitions.py to GradeScope (testcases will be released on Friday).

1. Smallest Partition

The function minpartition(n) returns a string depicting the smallest partition of n into squares.

>>> print(minpartition(10))
10=3^2+1^2

>>> print(minpartition(12))
12=2^2+2^2+2^2

2. Number of Partitions

>>> numpartitions(4)
2

>>> numpartitions(9)
4

This is because 
4 = 2^2 = 1^2+...+1^2
9 = 3^2 = 2^2+2^2+1^2 = 2^2+1^2+...+1^2 = 1^2+...+1^2

Note 10=3^2+1^2=1^2+3^2 is considered one (not two) partitions.

Hint: the subproblem needs two dimensions, otherwise you can't avoid overcounting.