rangerll的部落格

題目是這樣的：
3 = 2+1 = 1+1+1 所以3有三種拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1

共七種
依此類推，請問一個指定數字NUM的拆解方法個數有多少個？
#請計算出Num=40共多少解法,需花多少時間( 須印出所有合法解法)
++++++++++++++++++++++++++++++++++++++++++

public class number2 {
    static int count=0;
    
    public static void main(String[] args) {
        
        long start=System.currentTimeMillis();
        
        
        int number=40;
        int position=1;
        int i;
        int[] array= new int[40];
        
        
        
for(i=number;i>0;i--)
        {
    array[0]=i;
    partition2(array,position,i,(number-i));
        }
   
   
        
        System.out.println("count="+count);
        
        long end=System.currentTimeMillis();
        long MillSeconds = end - start;
System.out.println("time="+MillSeconds+"MillSeconds");
        
    }
    
    
    public static void partition2(int array[],int position,int front,int remain)
    {
        
        boolean flag=true;
        array[position-1]=front;
        
        if(position==1)
        {System.out.print(front);}
        else{
    System.out.print("+"+front);
    }
        if(remain==0 ){count++;System.out.println("");}
        else{
    for(int j=front;j>0;j--)
    {
    if((remain-j)>=0){
   
    if(flag==false){
   
    printpos2(array,position);
    };
    partition2(array,position+1,j,remain-j);
    flag=false;
    }   
    }
        }
    }
    
    public static void printpos2(int array[],int pos)
    {
        
        for(int i=0;i        {
   
    if(i==0)
    {System.out.print(array[i]);}
    else
    {
    System.out.print("+"+array[i]);
    }
        }        
    }

}
+++++++++++++++++++++++++++++++++++++++++++

*拆解過程中,數字須由大到小

由前面的數字決定後面數字的大小

將前面的數字逐漸減一，使用recursive方法，算出後面的組合