Monday, August 17, 2015

MJ [14] Number of square sum partitions

Questions:
Given a number n, find number of ways to express n by a sum of squares. Eg., if n=8, n can be expressed as 1+1+1+1+1+1+1+1, 4+4, or 4+1+1+1+1. So it should return 3.

Method1:
  1. find all the squares not greater than n and construct vec
  2. follow the idea of Coin Change [3] to find the number of ways

Ref
[1] http://www.mitbbs.ca/article_t/JobHunting/33018361.html
[2] http://www.mitbbs.com/article_t/JobHunting/33010083.html
[3] http://likemyblogger.blogspot.com/2015/08/mj-13-coin-change.html

No comments:

Post a Comment