递归

 1 /*#include<stdio.h>
 2 #include<string.h>
 3 
 4 int cur;
 5 int a[20];
 6 
 7 void fun(int n)//不重复递归，即0,1 递归
 8 {
 9     int i;
10     if(n==cur)
11     {
12         for(i=0;i<n;i++)
13             printf("%d",a[i]);
14         printf("\n");
15         return;
16     }
17     a[n]=0;
18     fun(n+1);
19 
20     a[n]=1;
21     fun(n+1);
22 }
23 
24 int main()
25 {
26     while(scanf("%d",&cur))
27     {
28         memset(a,0,sizeof(a));
29         fun(0);
30     }
31     return 0;
32 }*/
33 
34 
35 
36 /*公司发了某商店的购物券1000元，限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…，要求程序列出所有的正好能消费完该购物券的不同购物方法。
37 程序输入：
38 重复递归*/
39 #include<stdio.h>
40 #include<string.h>
41 
42 int m;
43 int price[1000];
44 int cur;
45 int count[1000];
46 int ans[1000][1000];
47 int sum;
48 int num;
49 
50 void fun(int cur,int money)
51 {
52     int i;
53     if(sum==money)
54     {
55         for(i=0;i<m;i++)
56             ans[num][i]=count[i];
57         ++num;
58         return;
59     }
60     if(sum>money||cur>=m)
61         return;
62 
63     sum+=price[cur];
64     count[cur]++;
65     fun(cur,money);
66 
67     sum-=price[cur];
68     count[cur]--;
69     fun(cur+1,money);
70 }
71 
72 int main()
73 {
74     int i,j;
75     while(scanf("%d",&m))
76     {
77         for(i=0;i<m;i++)
78             scanf("%d",&price[i]);
79         sum=num=0;
80         memset(ans,0,sizeof(ans));
81         memset(count,0,sizeof(count));
82           fun(0,1000);
83           printf("%d\n",num);
84           for(i=num-1;i>=0;i--)
85           {
86               for(j=0;j<m;j++)
87                   printf("%d ",ans[i][j]);
88               printf("\n");
89           }
90     }
91     return 0;
92 }
93