问题描述：给出n，sum。类似于杨辉三角，让你求出最顶尖为sum的第n层所有元素。

注意：答案有多种的按照字典序较小的那个输出。

题目链接：点击打开链接

思路：

通过简单分析不难发现，sum = C（i - 1， j - 1）* x； x = {0,1，......9}；

代码：

大牛的：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
typedef long long LL;
using namespace std;
int a[15],f[15];
int n,sum;
int solve()
{
    int s=0;
    for(int i=0;i<n;i++)
        s+=f[i]*a[i];
    return s;
}
int main()
{
   while(~scanf("%d%d",&n,&sum))
   {
       for(int i=0;i<n;i++)
          a[i]=i+1;
       memset(f,0,sizeof(f));
       f[0]=1;
       for(int i=1;i<n;i++)
       {
           for(int j=i;j>=1;j--)
              f[j]+=f[j-1];//杨辉三角
       }
       while(solve()!=sum)
          next_permutation(a,a+n);
       for(int i=0;i<n;i++)
           printf(i==n-1?"%d\n":"%d ",a[i]);
   }
   return 0;
}

MY：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MAX 30000

using namespace std;
int sum, n, res[100];
bool booll[100], flag = false;

int c(int n,int m){
        int a=1;
        if(m==0)
           return 1;
        for(int i=1;i<=m;i++){
            a=a*(n-i+1);
            a=a/i;//求组合数的一个技巧
        }
        return a;
}

void DFS(int dep, int he){
    if(he > sum)
        return;
    if(dep == n){
        if(sum == he && !flag){
        //flag!!!
            flag = true;
            cout << res[0];
            for(int i = 1; i < n; i++)
                cout << ' ' << res[i];
            cout << endl;
        }
        return;
    }
    for(int j = 1; j <= n; j++){
        if(!flag)
        if(!booll[j]){
            res[dep] = j;
            booll[j] = true;
            //c(n-1,m-1)表示杨辉三角中第n行第m个元素
            DFS(dep + 1, he + c(n - 1, dep) * j);
            booll[j] = false;
        }
    }
}

int main(){
    cin >> n >> sum;
    memset(booll, false, sizeof(booll));
    DFS(0, 0);
    return 0;
}