AcWing 170. 加成序列
原题链接
简单
作者:
十六
,
2021-01-21 11:46:28
,
所有人可见
,
阅读 324
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100+10;
int n, d;
int p[MAX];
bool dfs(int k){
if(k==d) return p[k]==n;
bool f[MAX] = {false};
for(int i=k; i>0; i--){
for(int j=i; j>0; j--){
int t = p[i]+p[j];
if(f[t] || t>n || t<=p[k]) continue;
f[t] = true;
p[k+1] = t;
if(dfs(k+1)) return true;
}
}
return false;
}
int main(){
p[1] = 1;
while(scanf("%d", &n), n){
d = 1;
while(!dfs(1)) d++;
for(int i=1; i<=d; i++) printf("%d ", p[i]);
cout<< endl;
}
return 0;
}