把Ｎ拆分为若干个数的和

问题描述：
　　给定一个正整数Ｎ，假设 0<A1<=A2<=A3...<=As 满足 A1+A2+A3+...+As=Ｎ，那么我们称序列A1 A2……As 为Ｎ的一个拆封。现在要求Ｎ的拆分数目。例如：当Ｎ= 6 时
6 = 1 + 1 + 1 + 1 + 1 + 1
  = 1 + 1 + 1 + 1 + 2
  = 1 + 1 + 2 + 2
  = 2 + 2 + 2
  = 1 + 1 + 1 + 3
  = 1 + 2 + 3
  = 3 + 3
  = 1 + 1 + 4
  = 2 + 4
  = 1 + 5
  = 6
　　所以 6 的整数拆分个数为 11。
 
{
  Problem   : N = A1 + A2 ... + As
  Algorithm : Depth First Search
  Author    : tenshi
  Date      : 2002-07-15 @ SJTU ZZL 111
}
Program N_Sum;
const n=6;
var
  a:array[1..n] of integer;  { 保存单个拆分。n最多拆封为n个1，所以s<=n }
  total:integer;             { 方案总数 }
  
  procedure output(s:integer); { 输出。 s为一个拆分的长度 }
  var i:integer;
  begin
    write(n,' =',a[1]:3);
    for i:=2 to s do write(' +',a:3);
    writeln;    
  end;
  
  
  procedure dfs(d,low,rest:integer);   { low为当前a[d]的下界,rest为还剩下多少要拆分 }
  var i:integer;
  begin
    if(rest=0) then {找到一组解}
    begin
      inc(total);
      output(d-1);
    end;
    if( low>rest ) then exit;
    {rest已经不能满足low的要求了，所以退出}
    for i:=low to rest do
    begin
      a[d]:=i;
      dfs(d+1,i,rest-i);
    end;
  end;
  
  begin
    dfs(1,1,n);
    writeln('Total = ',total);
  end.