从1到N共N个整数,请打印出利用这N个整数任意多个相加结果等于N + 1的所有可能性。每个数字只出现一次。
请用递归的思想写出代码!

解决方案 »

  1.   

    答:递归与栈的应用. 典型的整数拆分,数字不重复.
    参考代码
    //整数N+1的拆分1---N中数字和,数字不重复出现public class Split1
    {
     static int[] stack = new int[1000];//定义栈最大100
     static int top = -1;//栈顶指针
     static int n;//对n进行拆分
     public static void main(String[] args)
     {
       n=7;
       split(n);//对n进行拆分
      }//main
      
    static void split(int n)
     {
       split(n,1);//对n进行拆分。
    }//splitstatic void split(int n,int k)
     {//对n进行拆分。从K开始  if( n<=0 )
      {//
         printStack();//栈中已有一个拆分。打印出来
         return ;
       }
      for(int i=k;i<=n;i++)  
      {
        stack[++top]=i;//i已拆分出。进栈。
        split(n-i, i+1 );//对剩下的n-i继续拆分
        top--;//i出栈。继续下一个i-1的拆分。
       }//for(i)
    }//splitstatic void printStack()
    {
       if(top==0) return;//只有一个元素,不用打
       System.out.print(n+"=");
       for( int i=0;i<=top-1;i++ )
       {
         System.out.print(stack[i]+"+");
       }//for
       System.out.print(stack[top]+"\n");
     }//printStack
    }//class程序运行结果:
    7=1+2+4
    7=1+6
    7=2+5
    7=3+4