hello everyone . i have tried to solve this problem using dfs method. but it becomes extremely slow after input is >= 25. how do i make it faster. can u give me hints......
Code: Select all
# include <iostream>
# include <vector>
using namespace std;
int a[10000],p[10000],n,m=99999999;
void dfs(int sum,int s)
{
if(sum==n)
{
if(s<m){
m=s;
for(int j=0;j<s;j++) p[j]=a[j];
}
return;
}
for(int i=s-1;i>=0;i--)
{
if((sum+a[i])<=n){
a[s]=sum+a[i];
dfs(sum+a[i],s+1);
}
}
}
int main()
{
int i;
while(cin>>n)
{
m=99999999;
a[0]=1;
dfs(1,1);
for(i=0;i<m;i++)
cout<<p[i]<<' ';
cout<<'\n';
}
return 0;
}