回溯法解决整数划分
/** * * @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++;}}}}