POJ3187 Backward Digit Sums

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 int lev[12][12];
 8 int box[12];
 9 int n,s;
10 
11 
12 void solve(){
13     int sum;
14     lev[1][1]=1;
15     for(int i=2;i<=10;i++){
16         for(int j=1;j<=i;j++){
17             if(j==1||j==i) lev[i][j]=1;
18             else{
19                 lev[i][j]=lev[i-1][j-1]+lev[i-1][j];
20             }
21         }
22     }
23     scanf("%d%d",&n,&s);
24     for(int i=1;i<=n;i++){
25         box[i]=i;
26     }
27     do{
28         sum=0;
29         for(int i=1;i<=n;i++){
30             sum+=box[i]*lev[n][i];
31         }
32         if(sum==s) break;
33     }while(next_permutation(box+1,box+n+1));
34     for(int i=1;i<=n;i++){
35         printf("%d%c",box[i], i == n ? ‘\n‘ : ‘ ‘);
36     }
37 }
38 
39 int main (){
40     solve();
41     return 0;
42 }