#include <stdio.h>
#include <stdlib.h>
void fun(int in[],int *,int *,int*,int *);
int main(int argc, char** argv)
{
int top,count,sum,n;
int i;
int * arr;
bool bfinish;
bfinish = false;
while(!bfinish)
{
top = -1;
count = 0;
sum = 0;
printf("Please input n:");
scanf("%d",&n);
if (!n) bfinish = true;
else bfinish = false;
arr = (int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++) arr[i]=0;
fun(arr,&top,&count,&sum,&n);
printf("total:%d\n",count);
delete []arr;
}
return 0;
}
// 计算总和
// 输入:和因子栈in,栈顶指针top,方法计数指针count,总和指针 sum,指定的数n
// 输出:和因子栈in,栈顶指针top,方法计数指针count,总和指针 sum,指定的数n
void fun(int in[],int *top,int *count,int *sum,int* n)
{
int i,j;
if (*top <-1 || *n < 0) return;
if (1 == *n)
{
printf("1:1\n");
(*count)++;
return;
}
if (!(*n)) return;
if ((*sum) == (*n)) // 结束条件
{
(*count)++; // 方法总类增加一个
printf("%d:",*count);
for(j=0;j <= (*top);j++) // 打印结果
{
printf("%d ",in[j]);
}
printf("\n");
(*sum) -= in[(*top)--]; // 回溯,还原栈
return;
}
if ((*sum) > (*n)) // 总和过大 回溯 还原栈
{
(*sum) -= in[(*top)--];
return;
}
for(i=1;i<*n;i++)
{
if ( (*top) >= 0 && i < in[(*top)]) continue;
(*sum) += i; // 总和累加
in[++(*top)] = i; // 数值入栈
fun(in,top,count,sum,n); // 深层递归
}
(*sum) -= in[(*top)--]; // 本层结束,回溯
}