鼻マーガリンコミュの私事です。

int ans[255];/*分割結果を格納する外部変数*/

void putans(int n){
/*外部変数、配列ansに格納された値を表示する*/
int i;
for(i=0; i<n-1; ++i)
printf("%d + ",ans[i]);
printf("%d\n",ans[n-1]);
}

int part(int total, int min, int divNum){
int sub;
int cnt = 0;
if(total==0){
putans(divNum);
cnt = 1;
}else{
for(sub=min; sub<=total; sub++){
ans[divNum] = sub;
cnt += part(total-sub,sub+1,divNum+1);
}
}
return cnt;
}

int main(void){
int n;
printf("n: ");
scanf("%d",&n);
printf("total number = %d\n",part(n,1,0));
return 0;
}

#include<stdio.h>
#define NYet 0
#define Done 2
#define MaxX 10
#define MaxY 10

int sX,sY;
int place[MaxX+2][MaxY+2];
int pathnum(int x,int y){
/*(x,y)から右上へ行く経路の総数を求める*/
int num;
if(x==sX && y==sY) return 1;
/*1つの経路が見付かった*/

if(place[x][y] == Done) return 0;
/*通過済点:それ以上試さない*/
++place[x][y];
/*未通過点、さらに試してみる*/
num = pathnum(x+1,y) + pathnum(x,y+1) + pathnum(x-1,y) + pathnum(x,y-1);
--place[x][y];
return num;
}

int main(void){
int i,j;
/*格子数を設定*/
printf("sX: ");
scanf("%d",&sX);
printf("sY: ");
scanf("%d",&sY);

/*格子点を未通過にする(初期化)*/
for(i=1;i<=sX;i++){
for(j=1;j<=sY;j++){
place[i][j] = NYet;
}
}

/*格子点の外側を通過済にする進路可能判定を簡単にするため*/
for(i=1;i<=sX;i++){
place[i][0] = place[i][sY+1] = Done;
}
for(i=1;i<=sY;i++){
place[0][i] = place[sX+1][i] = Done;
}

printf("number of paths in %d x %d rectangle: %d\n",sX,sY,pathnum(1,1));
return 0;
}
int ans[255];

void putans(int n){
int i;
for(i=0; i<n-1; ++i)
printf("%d^2 + ",ans[i]);
printf("%d^2\n",ans[n-1]);
}

int part(int total,int min,int divNum){
/*数totalをmin以上の数での分割方法の数*/
int sub;
int cnt=0;
if(total==0){
putans(divNum);
cnt=1;
}else{
for(sub=min;sub*sub<=total;sub++){
ans[divNum]=sub;
cnt+=part(total-sub*sub,sub+1,divNum+1);
}
}
return cnt;
}

int main(void){
int n;
printf("n: ");
scanf("%d",&n);
printf("total number = %d\n",part(n,1,0));
return 0;
}