POJ3187 Backward Digit Sums

全列挙。next_permutationを使うとらく。やるだけです。

ちょっと数学力が足りないのでせこい技を使ってしまった。

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

int main(){
  int n,sum;
  int d[12];
  int c[12][12] = {0};
  c[0][0] = 1;
  c[1][0] = 1;
  c[1][1] = 1;
  
  scanf("%d%d",&n,&sum);
  for(int i = 2;i < n;i++){
    for(int j = 0;j <= i;j++){
      if(j == 0){
	c[i][j] = 1;
      }else{
	c[i][j] = c[i-1][j-1] + c[i-1][j];
      }
    }
  }
     
  for(int i = 1;i <= n;i++){
    d[i-1] = i;
  }
  
  do{
    
    int t = 0;
    
    for(int i = 0;i < n;i++){
      t += d[i] * c[n-1][i];
    }
    
    if(t == sum) break;

  }while(next_permutation(d,d + n));
      
  for(int i = 0;i < n;i++){
    cout << d[i] << " ";
  }
  cout << endl;
  
  return 0;
  
}