学步园

整数的任意拆分问题（不允许重复）

问题：输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数(不许重复), 使其和等于m （m<=1+2+...n）,要求将其中所有的可能组合列出来.

分析：记整数p可以用1,2...q的所有不重复数之和表示的组合为C(p,q)，则C(p,q)可以表示为以下的组合：
{q} + C(p-q,q-1)  (如果q<=m)
或者
C(p,q-1)
即要么包含q，要么不包含q。

另外有C(0,K)={},  C(K,0)无解(K>0)

因此可以使用动态规划的方法解决。

（要允许重复，可以参考我的另一篇blog。）

import java.util.ArrayList;<br /> import java.util.List;</p> <p>/**<br /> *<br /> * @author ljs 2011-05-11<br /> *<br /> * 输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数(不许重复), 使其和等于m （m<=1+2+...n）,要求将其中所有的可能组合列出来.<br /> *<br /> */<br /> public class SumPartition {<br /> private Object[][] C;<br /> private int m;<br /> private int n;</p> <p> public void sumPartitions(int m,int n){<br /> this.m = m;<br /> this.n = n;</p> <p> C = new Object[m+1][n+1];<br /> //C[1][1]=new int[][]{{1}};</p> <p> //do the loop column by column<br /> for(int col=1;col<=n;col++) {<br /> for(int row=1;row<=m;row++){<br /> List<int[]> combines = new ArrayList<int[]>();</p> <p> //calculate {n} U C(row-col,col-1)<br /> if(col<row){<br /> if(col>1){//when col==1, there is no solution<br /> Object[] C0 =(Object[])C[row-col][col-1];</p> <p> for(int i=0;i<C0.length;i++){<br /> int[] C0item = (int[])C0[i];</p> <p> //add n<br /> int[] cElementNew = new int[C0item.length+1];<br /> System.arraycopy(C0item, 0, cElementNew, 0, C0item.length);<br /> cElementNew[C0item.length] = col;<br /> combines.add(cElementNew);<br /> }<br /> }<br /> }else if(col==row){<br /> combines.add(new int[]{col});<br /> }</p> <p> //calculate C(row,col-1)<br /> //note: C(0,K) = {}; C(K,0) has no solution when K>0<br /> if(col>1){<br /> Object[] C1 =(Object[])C[row][col-1];<br /> for(int i=0;i<C1.length;i++){<br /> int[] C11 = (int[])C1[i];<br /> combines.add(C11);<br /> }<br /> }<br /> C[row][col] = combines.toArray();<br /> }<br /> }<br /> }<br /> public void printSize(){</p> <p> Object[] ci = (Object[])C[m][n];</p> <p> System.out.println("m:"+ m + ",n=" + n + " size:" + ci.length);<br /> }<br /> public void prettyPrint(){<br /> //for(int i=0;i<=m;i++){<br /> Object[] ci = (Object[])C[m][n];<br /> System.out.print("{");<br /> for(int j=0;j<ci.length;j++){<br /> int[] cij = (int[])ci[j];<br /> System.out.print("{");<br /> for(int k=0;k<cij.length-1;k++)<br /> System.out.print(cij[k] + ",");<br /> if(cij.length-1>=0)<br /> System.out.print(cij[cij.length-1]);<br /> System.out.print("}");<br /> }<br /> System.out.print("}");</p> <p> //System.out.print(" m:"+ m + ",n=" + n + " size:" + ci.length);</p> <p> System.out.println();<br /> //}<br /> }</p> <p> public static void main(String[] args) { </p> <p> SumPartition sp = new SumPartition();</p> <p> int m=6;<br /> int n=5;<br /> sp.sumPartitions(m,n);<br /> sp.printSize();<br /> sp.prettyPrint();</p> <p> m = 20;<br /> n=10;<br /> sp.sumPartitions(m,n);<br /> sp.printSize();<br /> }<br /> }<br />

测试输出：

 m:6,n=5 size:3
{{1,5}{2,4}{1,2,3}}

m:20,n=10 size:31

本实现中的row相当于上面讨论中的p， col相当于q。该算法的时间复杂度为O(mn)。