python整数划分，递归算法

• 问题描述
• 思路
• 代码
• 运行结果

正整数n，n=m₁+m₂+…+m_k，其中m_i为正整数，并且1≤m_i≤n，集合{m₁，m₂，…，m_k}是整数n的一个划分。
输入一个不小于10的整数，输出其所有整数划分。

将整数n划分，假设某种划分中m为最大的整数，则：
n可分为n-m，m，（n-m）再由(m-1)划分
(n-m)可分为(n-m-(m-1)),(m-1)，(n-m-(m-1)) 再由(m-2)划分
……
以此类推，直到m=0，停止划分，这样就将规模减小
if(n==0) return
if(m>1) f(n,m-1)
if(m<=n) f(n-m,m)

def division(n, m, string):
    if n == 0:
        print(string)
    else:
        if m>1:
            division(n, m-1, string)
        if m <= n:
            division(n-m, m, str(m)+ ' '+string) 
        
print('输入一个不小于10的整数：')
n = int(input())
m=n
print('%d的划分如下：'%n)
division(n, m, '')