杨辉三角及普通枚举应用

大佬们，放过我这个啥也不会、啥也不懂的蒟蒻吧！！！

首先，这道题最开始要解决的便是由几个数推出来的最后一个数； 先举个栗子

同志们，发现最后结果的特点了吗？？？

那就是

满足杨辉三角的系数

那么便有如下推导方式

再加上明显可以压缩空间变为一维数组 故最后的方程就是

f[j]+=f[j-1]

啥子?问我为啥要用j??f我不会告诉你是从右往左刷的

于是乎，可以预处理一哈

	memset(c,0,sizeof(c));
	c[1]=1;
	for(int i=2;i<=n;i++)
		for(int j=i;j>=1;j--)
			c[j]+=c[j-1];

也就是说a[i]来存数，而c[i]表示最后的系数 然后运用一下系统里的next_permutation(a+1,a+n+1)来列举全排列，然后你会惊奇的发现，这题基本就完了？？？

然鹅

时间会爆掉 于是就要进行剪枝操作，吼吼吼，具体如何剪枝你猜啊！！！ 代码放上

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int maxn=20;
int a[maxn];
int c[maxn];
int n,sum;
bool comp(int x,int y)
{
	return x>y;
}
main()
{
	cin>>n>>sum;
	for(int i=1;i<=n;i++)
		a[i]=i;
	memset(c,0,sizeof(c));
	c[1]=1;
	for(int i=2;i<=n;i++)
		for(int j=i;j>=1;j--)
			c[j]+=c[j-1];
	do
	{
		int s=0;
		bool flag=false;
		for(int i=1;i<=n;i++)
		{
			s+=a[i]*c[i];
			if(s>sum)
			{
				flag=true;
				sort(a+i,a+n+1,comp);
				break;
			}
		}
		if(flag)continue;
		if(s==sum)
		{
			for(int i=1;i<=n;i++)
				cout<<a[i]<<' ';
			cout<<endl;
			break;
		}
	}while(next_permutation(a+1,a+n+1));
	return 0;
}