资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
例如:
3 1 2 4
4 3 6
7 9
16
现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
输入格式
第1行为两个正整数n，sum
输出格式
一个1～N的一个排列
样例输入
4 16
样例输出
3 1 2 4
数据规模和约定
0<n<=10
思路：
我们将解题看成两个部分：
一个是满足题目要求的相邻两数相加，一直得到最后一个数，跟输入给的数相等；
一个是满足在给定的个数内输出最小的满足要求的序列
所以也就有了下面的两个函数，f（）对应条件一，dfs用来顺序遍历；
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10+10;
int n,m,t,d;
int a[N],b[N],flag[N];
int if_end = 0;
string s;
bool f(){
int temp[N];//合并只是一个判断条件，为了不破坏原数组的输出，用临时数组存一下。
for(int i=0;i<n;i++){
temp[i] = a[i];
}
int x = n-1; //合并次数会比数字个数少一
while(x){
for(int i=0;i<x;i++){
temp[i] = temp[i]+temp[i+1];
}
x--;
}
if(temp[0]==m)return true;
return false;
}
void dfs(int u){
if(u==n&&f()){ //搜索到序列的最后一个数字，并且满足相加的最终结果要求。
if_end = 1; //判断是否已经找到这样的序列了，就停止搜索。
for(int i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
}
for(int i=1;i<=n;i++){//从1开始为序列中每个数字赋值；
if(if_end)break;
if(!flag[i]){ //flag数组记录某一次的序列中各个数字的使用情况，从小到大也满足了输出字典序最小；
a[u] = i;
flag[i] = 1; //标记当前i已经被前面的数字使用了
dfs(u+1); //搜索序列的下一个数字
flag[i]=0; //回退到上一个状态，恢复数字的标记(前面的序列不满足要求，改变次位上数字的取值；)
}
}
}
signed main(){
cin>>n>>m;
dfs(0);
return 0;
}