/*中國系統分析員顧問團，http://www.csai.cn*/
/*程序員下午考試指南書籍源碼*/

#include <stdio.h>
#define N 100
int a[N];

int sum(int total, int d[],int n){ 
int s, p, t, b[N], none = 1;
b[0] = 0;  t = d[0]; p = 1;
do{
if (t == total){ /* 找到了一個解，把當前解輸出 */
printf("%4d = %d",total, d[b[0]]);
for(s = 1; s < p; s++)
printf(" +%d",d[b[s]]);
printf("\n");
none = 0;   /*  置找到過解的標志  */
}
else {
for(s = b[p-1] + 1; s < n-1 && t + d[s] > total;s++);
if (s < n && t + d[s] <= total) {
b[p++] = s;  t += d[s];
continue; 
}
}
t -= d[b[p-1]];     /*  回溯 */
if ( p > 1 && b[p-1] == n-1){
p--; t -= d[b[p-1]];
}
if ( p == 1 && b[0] == n-1) break;  /*  回溯到底，退出找解循環  */
t += d[++b[p-1]]; /*  回溯后，調整  */
} while(1);
return !none; /* 返回找到過解答的標志  */
}

main( ){ 
int i,n, total, d;
printf("輸入  total!\n"); scanf("%d",&total);
printf("輸入  n!\n");  scanf("%d",&n);
for(i = 0; i < n;) {
printf("輸入數組的第 %d 個正整數( > 0 且 <= %d)\n",i+1,total);
scanf("%d", &d);
if (d < 1 || d > total){
printf("出錯，請重新輸入！\n");
continue;
}
a[i++] = d;
}
if (!sum(total, a, n)) printf("沒有找到解答！\n");
printf("\n\n");
}