AcWing 170. 加成序列 -C++DFS
原题链接
简单
作者:
LeeDV
,
2024-04-11 21:09:07
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
int path[N];
int n;
bool dfs(int u,int depth)
{
if(u>depth)return false;
if(path[u-1]==n)return true;
bool st[N]={0};//避免重复计数
for(int i=u-1;i>=0;i--)
{
for(int j=i;j>=0;j--)
{
int tmp=path[i]+path[j];
if(tmp>n||tmp<=path[u-1]||st[tmp])continue;
st[tmp]=true;
path[u]=tmp;
if(dfs(u+1,depth))return true;
}
}
return false;
}
int main()
{
path[0]=1;
while(cin>>n,n)
{
int depth=1;
while(!dfs(1,depth)) depth++;
for(int i=0;i<depth;i++)printf("%d ",path[i]);
printf("\n");
}
return 0;
}