问题出于codewars，简言之：寻找和为一个整数的的不同整数组合。https://en.wikipedia.org/wiki/Partition_(number_theory)
例如：和为6的整数组合有如下11种，
6
5 + 1
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
解法一：
为了避免重复，我们可以选择逐渐递减第一个加数，直到不小于ｎ的一半（保持分解的数字），然后对第一个加数应用这个策略，还是以６为例：
6
5 + 1
4 + 2
3 + 3
然后对第一个加数５应用这个策略，
4 + 1
3 + 2
接着对分解４和３应用这一策略，得到如下：
6
5 + 1
4 + 1 + 1
3 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1
3 + 2 + 1
4 + 2
2 + 2 + 2
3 + 3
因为我们已经有了３＋２＋１，对于４而言就不在分解成３＋１＋２，此处的限制条件分解４不能产生比２（４后面的２）小的数字，所以只能是２＋２，同理，３就不再分解了，因为分解不出比３（后面那个）还大的数了。
def exp_sum(n):
if n < 0:
return 0
if n == 0:
return 1
return help(n, 1)
def help(n, mini):
tmp = 1
if n <= 1:
return 1
for i in range(1, n/2+1):##保证n-i不小于ｉ
if i >= mini: ＃＃保证分解得到的数不小于后面的较小的数
tmp = tmp + help(n-i, i)
return tmp
print exp_sum(6)
当然了，这个递归的速度是很慢的，T(n) = T(n-1) + T(n-2) +...+ T(ceil(n/2))，时间复杂度是指数级别的。
解法二：
可以开辟一个大小为ｎ的list存储已经计算的结果：
def exp_sum(n):
if n < 0:
return 0
if n == 0 or n == 1:
return 1
solution = [1] + [0]*n
for i in range(1, n):
for j in range(i, n+1):
solution[j] += solution[j-i]
return solution[n]+1
解法三：
根据*上的generation function：p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ... + (-1)^(k+1)*p(k − (3k^2 - k)/2) + (-1)^(k+1)*p(k − (3k^2 + k)/2)
def exp_sum(n):
solutions = [1]*(n + 1)
for i in xrange(1, n + 1):
j, k, s = 1, 1, 0
while j > 0:
j = i - (3 * k * k + k) / 2
if j >= 0:
s += (-1) ** (k+1) * solutions[j]
j = i - (3 * k * k - k) / 2
if j >= 0:
s += (-1) ** (k+1) * solutions[j]
k += 1
solutions[i] = s
return solutions[n]
参考链接：
https://en.wikipedia.org/wiki/Partition_(number_theory)
http://*.com/questions/438540/projecteuler-sum-combinations
2015-07-15 17:03:25