分解和为N的所有加数的情况

/**
 * http://zjfhw.iteye.com/blog/2213877
 * 分解和为N的因子
 * 思路：
 * 和为N的因子 必然可以分成N组
 * 比如5
 * 因子数为5的组：1+1+1+1+1
 * 因子数为4的组：1+1+1+1   然后剩余的1 分配给任意一组 2+1+1+1 1+2+1+1 （如果位置不同算为2组的话）
 * 因子数为3的组：1+1+1   剩余2 ，问题变成 如何将2个1 分配给 3个组 
 * ......
 * 
 * 因子数为1的组：5
 */
public class ResolveSum {
	static int[] arr ;
	
	public static void main(String[] args) {
		//要分解的和为10
		int n = 10;
		//将10转化成 一个长度为n的数组 每个元素都为1
		arr =getData(n);
		//分别去求因子个数为i的因子集 i=1~n
		for(int i=1;i<=arr.length;i++){
			resolveSum(1,0,i,arr.length);
			clear(arr);
		}
	}
	/**
	 * 分解
	 * @param index 往第index个位置分发1
	 * @param payd 计数器，已经分发了payd个1
	 * @param group 该组有group个元素
	 * @param N 要分解的和
	 */
	static void resolveSum(int index,int payd,int group,int N){
		//循环着进行分发，覆盖  “n个数分发到m个地方” 的所有情况
		for(int i=payd;i<N-group;i++){
			//首先将第index个位置分发1
			arr[index-1]+=1;
			if(i==N-group-1){
				//当剩余值已经分发完，将该组因子打印出来
				printElement(arr,group);
				//将最后操作的位置还原成1 
				arr[index-1]=1;
			}else{
				//否则开始向index+1的位置进行分发，如果已经超出了该组的因数个数，则不操作
				if(index+1<=group)
				resolveSum(index+1,i+1,group,N);
			}
		}	
		
		
	}
	private static void printElement(int[] arr2, int group) {
		System.out.print(arr2.length+"=");
		for(int i=0;i<group;i++){
			System.out.print(+arr2[i]+ (i==group-1?"":"+"));
		}
		System.out.println("");
			
	}
	
	public static int[] getData(int n){
		int[] data = new int[n];
		for(int i=0;i<data.length;i++){
			data[i] = 1;
		}
		return data;
	}
	
	public static void clear(int[] data){
		for(int i=0;i<data.length;i++){
			data[i] = 1;
		}
	}
}

 

 

结果：（没有考虑 加数一样但位置不同的情况，视具体问题进行修改吧...很简单）

 

10=10

10=2+8

10=3+7

10=4+6

10=5+5

10=6+4

10=7+3

10=8+2

10=9+1

10=2+2+6

10=2+3+5

10=2+4+4

10=2+5+3

10=2+6+2

10=2+7+1

10=3+2+5

10=3+3+4

10=3+4+3

10=3+5+2

10=3+6+1

10=4+2+4

10=4+3+3

10=4+4+2

10=4+5+1

10=5+2+3

10=5+3+2

10=5+4+1

10=6+2+2

10=6+3+1

10=7+2+1

10=8+1+1

10=2+2+2+4

10=2+2+3+3

10=2+2+4+2

10=2+2+5+1

10=2+3+2+3

10=2+3+3+2

10=2+3+4+1

10=2+4+2+2

10=2+4+3+1

10=2+5+2+1

10=2+6+1+1

10=3+2+2+3

10=3+2+3+2

10=3+2+4+1

10=3+3+2+2

10=3+3+3+1

10=3+4+2+1

10=3+5+1+1

10=4+2+2+2

10=4+2+3+1

10=4+3+2+1

10=4+4+1+1

10=5+2+2+1

10=5+3+1+1

10=6+2+1+1

10=7+1+1+1

10=2+2+2+2+2

10=2+2+2+3+1

10=2+2+3+2+1

10=2+2+4+1+1

10=2+3+2+2+1

10=2+3+3+1+1

10=2+4+2+1+1

10=2+5+1+1+1

10=3+2+2+2+1

10=3+2+3+1+1

10=3+3+2+1+1

10=3+4+1+1+1

10=4+2+2+1+1

10=4+3+1+1+1

10=5+2+1+1+1

10=6+1+1+1+1

10=2+2+2+2+1+1

10=2+2+3+1+1+1

10=2+3+2+1+1+1

10=2+4+1+1+1+1

10=3+2+2+1+1+1

10=3+3+1+1+1+1

10=4+2+1+1+1+1

10=5+1+1+1+1+1

10=2+2+2+1+1+1+1

10=2+3+1+1+1+1+1

10=3+2+1+1+1+1+1

10=4+1+1+1+1+1+1

10=2+2+1+1+1+1+1+1

10=3+1+1+1+1+1+1+1

10=2+1+1+1+1+1+1+1+1

 

最后再加上

10=1+1+1+1+1+1+1+1+1+1