5-3 自然数的拆分 (20 分)
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。 当n=7共14种拆分方法：
7=1+1+1+1+1+1+1
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
输入格式:
输入n， 1<n<20。
输出格式:
按字典序输出具体的方案。
输入样例:
在这里给出一组输入。例如：
7
输出样例:
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
这里我们同样采用回溯法；每个结点优先从1开始减去当前剩余数，减数优先级递减直到n-1结束；随后判断是否可减；当出现余数既不为0又小于当前减数时则判断不可减，减去当前分支；具体算法如下：
package 宿題;
import java.io.*;
public class PTASplittingNumbers {
static int A;
public static void main(String args[])throws IOException{
StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
A=(int)in.nval;
String s=""+A+"=";//初始化字符串s;
Split(A,1,s);
}
private static void Split(int a,int n,String s){
if(a==0){//当前余数为0，到达最底层；
s=s.substring(0, s.length()-1);//将字符串最后一个字符“+”舍去；
System.out.println(s);
}else{
for(int i=n;i<A;i++){
if(a-i>=i||a-i==0)//判断是否可减，否则剪枝；
Cut(a-i,i,s+i+"+");
}
}
}
该算法最坏情况下的时间复杂度为O((n-1)^n)。
}
