任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。 当n=7共14种拆分方法：

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

输入格式:

输入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)。

}

 

版权声明：本文为Modori原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Modori/p/11929511.html