整數劃分問題是算法中的一個經典命題之一，有關這個問題的講述在講解到遞歸時基本都将涉及。所謂整數劃分，是指把一個正整數n寫成如下形式：
n=m1+m2+...+mi; （其中mi為正整數，并且1 <= mi <= n），則{m1,m2,...,mi}為n的一個劃分。
如果{m1,m2,...,mi}中的最大值不超過m，即max(m1,m2,...,mi)<=m，則稱它屬于n的一個m劃分。這裡我們記n的m劃分的個數為f(n,m);
例如但n=4時，他有5個劃分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被認為是同一個劃分。
該問題是求出n的所有劃分個數，即f(n, n)。下面我們考慮求f(n,m)的方法;
---------------------------------------------------------------------
（一）遞歸法
根據n和m的關系，考慮以下幾種情況：
（1）當 n = 1 時，不論m的值為多少（m > 0 )，隻有一種劃分即 { 1 };
(2) 當 m = 1 時，不論n的值為多少，隻有一種劃分即 n 個 1，{ 1, 1, 1, ..., 1 };
(3) 當 n = m 時，根據劃分中是否包含 n，可以分為兩種情況：
(a). 劃分中包含n的情況，隻有一個即 { n }；
(b). 劃分中不包含n的情況，這時劃分中最大的數字也一定比 n 小，即 n 的所有 ( n - 1 ) 劃分。
是以 f(n, n) = 1 + f(n, n-1);
(4) 當 n < m 時，由于劃分中不可能出現負數，是以就相當于 f(n, n);
(5) 但 n > m 時，根據劃分中是否包含最大值 m，可以分為兩種情況：
(a). 劃分中包含 m 的情況，即 { m, { x1, x2, ..., xi } }, 其中 { x1, x2, ..., xi } 的和為 n - m，可能再次出現 m，是以是（n - m）的 m 劃分，是以這種劃分
個數為 f(n-m, m);
(b). 劃分中不包含 m 的情況，則劃分中所有值都比 m 小，即 n 的 ( m - 1 ) 劃分，個數為 f(n, m - 1);
是以 f(n, m) = f(n - m, m) + f(n, m - 1);
綜合以上情況，我們可以看出，上面的結論具有遞歸定義特征，其中（1）和（2）屬于回歸條件，（3）和（4）屬于特殊情況，将會轉換為情況（5）。而情況（5）為通用情況，屬于遞推的方法，其本質主要是通過減小m以達到回歸條件，進而解決問題。其遞推表達式如下：
f(n, m) = 1; ( n = 1 or m = 1 )
f(n, n); ( n < m )
1+ f(n, m - 1); ( n = m )
f(n - m, m) + f(n, m - 1); ( n > m )
是以我們可以給出求出 f(n, m) 的遞歸函數代碼如下（引用 Copyright Ching-Kuang Shene July / 23 / 1989 的代碼）：
計算f(n,m)，即n的m劃分的個數
unsigned long GetPartitionCount(int n, int max)
{
if (n == 1 || max == 1)
return 1;
else if (n < max)
return GetPartitionCount(n, n);
else if (n == max)
return 1 + GetPartitionCount(n, max-1);
else
return GetPartitionCount(n,max-1) + GetPartitionCount(n-max, max);
}
我們可以發現，這個命題的特征和另一個遞歸命題：
相似，也就是說，由于樹的“天然遞歸性”，使這類問題的解可以通過樹來展現，每一個葉子節點的路徑是一個解。是以把上面的函數改造一下，讓所有劃分裝配到一個.NET類庫中的TreeView控件，相關代碼（c#）如下：
組裝TreeView
/// <param name="root">樹的根結點</param>
/// <param name="n">被劃分的整數</param>
/// <param name="max">一個劃分中的最大數</param>
/// <returns>傳回劃分數，即葉子節點數</returns>
private int BuildPartitionTree(TreeNode root, int n, int max)
{
int count=0;
if( n==1)
{
//{n}即1個n
root.Nodes.Add(n.ToString());//{n}
return 1;
}
else if( max==1)
//{1,1,1,
,1} 即n個1
TreeNode lastNode=root;
for(int j=0;j<n;j++)
{
lastNode.Nodes.Add("1");
lastNode=lastNode.LastNode;
}
else if(n<max)
return BuildPartitionTree(root, n, n);
else if(n==max)
root.Nodes.Add(n.ToString()); //{n}
count=BuildPartitionTree(root, n, max-1);
return count+1;
else
//包含max的分割，{max, {n-max}}
TreeNode node=new TreeNode(max.ToString());
root.Nodes.Add(node);
count += BuildPartitionTree(node, n-max, max);
//不包含max的分割，即所有max-1分割
count += BuildPartitionTree(root, n, max-1);
return count;
}
如果我們要輸出所有解，隻需要輸出所有葉子節點的路徑即可，可以同樣用遞歸函數來輸出所有葉子節點（代碼中使用了一個StringBuilder對象來接收所有葉子節點的路徑）：
擷取所有葉子節點的路徑
private void PrintAllLeafPaths(TreeNode node)
//屬于葉子節點?
if(node.Nodes.Count==0)
this.m_AllPartitions.AppendFormat("{0}\r\n", node.FullPath.Replace('\\',','));
foreach(TreeNode child in node.Nodes)
this.PrintAllLeafPaths(child);
這個小例子的運作效果如下（源代碼都在文中，就不提供下載下傳連結）：
通過遞歸思路，我們給出了n的劃分個數的算法，也把所有劃分組裝到一棵樹中。好，關于遞歸思路我們就暫時介紹到這裡。關于輸出所有劃分的标準代碼在這裡省略了，我們有時間再做詳細分析。
（二）母函數法
下面我們從另一個角度即“母函數”的角度來考慮這個問題。
所謂母函數，即為關于x的一個多項式G（x）：
有 G（x）= a0 + a1*x + a2*x^2 + a3*x^3 + ...
則我們稱G（x）為序列（a0，a1，a2，...）的母函數。關于母函數的思路我們不做更多分析。
我們從整數劃分考慮，假設n的某個劃分中，1的出現個數記為a1，2的個數記為a2，..., i的個數記為ai，
顯然: ak<=n/k; (0<= k <=n)
是以n的劃分數f(n,n)，也就是從1到n這n個數字中抽取這樣的組合，每個數字理論上可以無限重複出現，即個數随意，使他們的總和為n。顯然，數字i可以有如下可能，出現0次（即不出現），1次，2次，..., k次，等等。把數字i用(x^i)表示，出現k次的數字i用 x^(i*k)表示， 不出現用1表示。例如數字2用x^2表示，2個2用x^4表示，3個2用x^6表示，k個2用x^2k表示。
則對于從1到N的所有可能組合結果我們可以表示為：
G(x) = (1+x+x^2+x^3+...+x^n) (1+x^2+x^4+...) (1+x^3+x^6+...) ... (1+x^n)
= g(x,1) g(x,2) g(x,3) ... g(x, n)
= a0 + a1* x + a2* x^2 + ... + an* x^n + ... ; （展開式）
上面的表達式中，每一個括号内的多項式代表了數字i的參與到劃分中的所有可能情況。是以該多項式展開後，由于x^a * x^b=x^(a+b)，是以 x^i 就代表了i的劃分，展開後(x^i)項的系數也就是i的所有劃分的個數，即f(n,n)=an （上式中g（x，i）表示數字i的所有可能出現情況）。
由此我們找到了關于整數劃分的母函數G（x）；剩下的問題是，我們需要求出G（x）的展開後的所有系數。
為此我們首先要做多項式乘法，對于我們來說并不困難。我們把一個關于x的一進制多項式用一個整數數組a[]表示，a[i]代表x^i的系數，即：
g(x) = a[0] + a[1]x + a[2]x^2 + ... + a[n]x^n;
則關于多項式乘法的代碼如下，其中數組a和數組b表示兩個要相乘的多項式，結果存儲到數組c：
多項式相乘，即c=a*b
#define N 130
unsigned long a[N];/*多項式a的系數數組*/
unsigned long b[N];/*多項式b的系數數組*/
unsigned long c[N];/*存儲多項式a*b的結果*/
/*兩個多項式進行乘法，系數分别在a和b中，結果儲存到c ，項最大次數到N */
/*注意這裡我們隻需要計算到前N項就夠了。*/
void Poly()
int i,j;
memset(c,0,sizeof(c));
for(i=0; i<N; i++)
for(j=0; j<N-i; j++) /*y<N-i： 確定i+j不會越界*/
c[i+j] += a[i]*b[j];
下面我們求出G（x）的展開結果，G（x）是n個多項式連乘的結果：
計算G（x）的前N項系數
/*計算出前N項系數！即g(x,1) g(x,2)... g(x,n)的展開結果*/
void Init()
int i,k;
memset(a,0,sizeof(a));
for(i=0;i<N;i++) a[i]=1; /*第一個多項式：g(x, 1) = x^0 + x^1 + x^2 + x^3 +
*/
for(k=2;k<N;k++)
{
memset(b,0,sizeof(b));
for(i=0;i<N;i+=k) b[i]=1;/*第k個多項式：g(x, k) = x^0 + x^(k) + x^(2k) + x^(3k) +
Poly(); /* 多項式乘法：c= a*b */
memcpy(a,c,sizeof(c)); /*把相乘的結果從c複制到a中：c=a; */
}
通過以上的代碼，我們就計算出了G（x）的展開後的結果，儲存到數組c中。此時有：f(n,n)=c[n];剩下的工作隻是把相應的數組元素輸出即可。
問題到了這裡已經解決完畢。但我們發現，針對該問題，g(x,k)是一個比較特殊的多項式，特點是隻有k的整數倍的索引位置有項，而其他位置都為0，具有項“稀疏”的特點，并且項次分布均勻（次數跨度為k）。這樣我們就可以考慮在計算多項式乘法時，可以減少一些循環。是以可以對Poly函數做這樣的一個改進，即把k作為參數傳遞給Poly：
改進後的多項式乘法
/*改進後，多項式a乘以一個有特殊規律的多項式b，即b中隻含有x^(k*i)項，i=0,1,2,
*/
/*如果b沒有規律，隻需要把k設為1，即與原來函數等效*/
void Poly2(int k) /*參數k的含義：表示b中隻有b[k*i]不為0！*/
for(j=0; j<N-i; j+=k)
這樣，原有的函數可以認為是k=1的情況（即多項式b不具有上訴規律）。相應的，在上面的Init函數中的調用改為Poly2(k)即可。
---------------------------------------------------------------------------------
參考資料：
（1）關于“遞歸”部分的代碼，參考了Ching-Kuang Shene，July/23/1989的代碼；
（2）關于“母函數”部分，參考了《Acm程式設計》（劉春英）（PPT文檔）；
（3）“母函數”方法的Init和Poly的代碼，參考了某位教師的代碼 : ymc 2008/09/25， 其中多項式乘法的改進是我提出的建議。
-- by hoodlum1980 2008-10-11