整数划分问题算法分析与实现（递归）

问题描述：

把一个正整数n写成多个大于等于1且小于等于其本身的整数的和，则其中各加数所构成的集合为n的一个划分。

把一个正整数n写成为 n=m1+m2+…+mi。其中，mi为正整数，并且1≤mi≤n；{m1，m2，…，mi}为n的一个划分。

如{m1，m2，…，mi}果中的最大值不超过m，即max(m1，m2，…，mi)≤m，则称它属于n的一个m划分。

关于整数划分和生成函数的具体概念请戳传送门：https://en.wikipedia.org/wiki/Partition_(number_theory)

实现如下：

1. 当n = 1时，无论m为何值，只有{1}一种划分
2. 当m = 1时，无论n为何值，只有{n}一种划分
3. 当n < m时，因为m为正整数，所以不可能出现负数情况，所以相当于IntegerPartition(n, n)
4. 当n == m时，细分为划分中是否包含n的情况
   • 当划分中包含n时，划分为{n}，一种情况
   • 当划分中不包含n时，划分中mi最大值一定小于n，则划分为IntegerPartition(n, m-1)
   • 此时IntegerPartition(n, m) = 1 + IntegerPartition(n, m-1)
5. 当n > m时，细分为划分中是否包含m的情况
   • 当划分中包含m时，划分为{m，{x1，x2，…，xi}}，此时划分为IntegerPartition(n-m, m)
   • 当划分中不包含m时，此时划分中的max一定小于m，此时划分为IntegerPartition(n, m-1)
   • 此时IntegerPartition(n, m) = IntegerPartition(n-m, m) + IntegerPartition(n, m-1)

//注意输入值的判断
//保证所有路径都有返回值
class Solution
{
public:
    int IntegerPartition(int n, int m)
    {
        if (n <  || m < ) return -;//防御性动作
        else if (n ==  || m == ) return ;
        else if (n < m) return IntegerPartition(n, n);
        else if (n == m) return  + IntegerPartition(n, m - );
        else if (n > m) return IntegerPartition(n - m, m) + IntegerPartition(n, m - );
    }
};