回溯法解决整数划分

/**
 * 
 * @author chenzhuzuo
 * 回溯法解决数字拆分问题
 * 问题描述：
 * 	整数的分划问题。 
	如，对于正整数n=6，可以分划为： 
	6 
	5+1 
	4+2, 4+1+1 
	3+3, 3+2+1, 3+1+1+1 
	2+2+2, 2+2+1+1, 2+1+1+1+1 
	1+1+1+1+1+1+1 
	现在的问题是，对于给定的正整数n,编写算法打印所有划分。
	用户从键盘输入 n （范围1~10）
程序输出该整数的所有划分。
 *
 *
 *以前做这个题时一直找不到好的思路，在网上也看了一下别人的做法，更多的是使用递归的算法，
 *看了还是不太明白，这几天研究了一下回溯算法，做了几个比较经典的题目，感觉本题可以用求
 *子集和的思路来解决，就试了一下，最后还是做出来了，不过效率不是很高。经过今天的学习
 *，感觉回溯法确实很难懂，但是一旦你弄懂了，回溯法可以说是万能的，真的很好用
 */
public class ShuziChaiFei {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		printResult(6);
	}
	/**
	 * 
	 * @param n对n进行拆分
	 */
	private static void printResult(int n){
		int a[]= new int[n+1];//用于记录每个数出现的个数（1=<i<=n）;
		for(int i=0;i<=n;i++){
			a[i]=0;
		}
		int sum=0;
		int k = 1;
		while(k>=1){
			a[k] += 1;
			sum+=k;
			if(sum==n){//如果当前的和等于n则获得一个解，输出
				for(int i=1;i<=k;i++){
					int m=1;
					//a[i]等值表示i在这个解中出现的次数
					while(m<=a[i]){
						if(m==a[i]&&i==k){
							System.out.print(i);
						    m++;
							
						    }
						    else{
						    	System.out.print(i+"+");
								m++;
						    	
						    }
					}
				}
				a[k]++;//继续搜索解空间
				sum+=k;
				System.out.println();
			}
			else if(sum>n){
				sum -= k;
				a[k] -=1;
				k++;
			}
			//当k>n时进行回溯
			if(k>n){
				k--;
				while(a[k]>0){
					sum=sum-a[k]*k;
					k--;
				}
				while(a[k]==0){
					k--;
					if(k<1){
						return;
					}
				}
				sum -= k;
				a[k]--;
				k++;
				
			}
		}
	}

}