Q. Given a number n, find a set such that –

- Sum of all the elements should result into n.
- Multiplication of all the elements should be greater than any other similar set (whose elements result n when summed up).

A. This is a very interesting problem as we have to go through every combination and calculate and compare the multiplication. Since, there is no restriction on the length of the subset, it makes problem much more interesting.

I propose use of dynamic programming here. We will start computing the f(n) from 1

At every stage, we have to compute all combinations of f(1).. f(n-1)

f(n) = max {

f(1) * f(n-1)

f(2) * f(n-2)

….. }

To avoid repeated operations, we can store start computing f(1).. f(n-1) one by one and do the book keeping of the result.