学步园

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

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

分析：记整数k的所有组合为C(k)，则K可以表示为以下的组合：
{K} U C(0)
{K-1} U C(1)
{K-2} U C(2)
....
{1} U C(k-1)

以上是K<=n的情况， 如果k>n，则K可以表示为以下的组合：
{n} U C(K-n)
{n-1} U C(K-n+1)
{n-2} U C(K-n+2)
....
{1} U C(k-1)

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

import java.util.ArrayList;<br /> import java.util.List;<br /> /**<br /> *<br /> * @author ljs 2011-05-11<br /> *<br /> * 输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数(允许重复取同一个数), 使其和等于m ,要求将其中所有的可能组合列出来.<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;<br /> C = new Object[m+1];<br /> C[0]=new int[][]{{}};<br /> C[1]=new int[][]{{1}};//C[2]=new int[][]{{1,1},{2}};<br /> for(int i=2;i<=m;i++){<br /> List<int[]> combines = new ArrayList<int[]>();<br /> int jStart = (i<=n)?i:n;<br /> for(int j=jStart;j>=1;j--){<br /> Object[] cArray = (Object[])C[i-j];<br /> for(int k=0;k<cArray.length;k++){<br /> int[] cElement = (int[])cArray[k];<br /> int[] cElementNew = new int[cElement.length+1];<br /> System.arraycopy(cElement, 0, cElementNew, 0, cElement.length);<br /> cElementNew[cElement.length] = j;<br /> combines.add(cElementNew);<br /> }<br /> }<br /> C[i] = combines.toArray();<br /> }<br /> }<br /> public void printSize(){<br /> Object[] ci = (Object[])C[m];<br /> 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];<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 /> }<br /> public static void main(String[] args) {<br /> SumPartition sp = new SumPartition();</p> <p> int m=5;<br /> int n=3;<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:5,n=3 size:13
{{2,3}{1,1,3}{3,2}{1,2,2}{2,1,2}{1,1,1,2}{1,3,1}{2,2,1}{1,1,2,1}{3,1,1}{1,2,1,1}{2,1,1,1}{1,1,1,1,1}}

m:20,n=10 size:521472

注意输出中重复的集合{2,3}和{3,2}, 还有{1,2,2}, {2,1, 2}。可以在最后加上去重复集合的功能过滤掉。