#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
vector <string> v;
int n;
void dfs(int cur_sum,int k,string s)
{
    string temp;
    if(cur_sum == n)
    {
        v.push_back(s);
        return;
    }
    if(cur_sum>n)
    {
        return;
    }
    temp = s + " + " + to_string(k+1);
    dfs(cur_sum+k+1,k+1,temp);

    temp = s + " * 2";
    dfs(cur_sum * 2,k,temp);
}
int main()
{
    cin.sync_with_stdio(false), cin.tie(0);
    while(cin>>n)
    {
       if(n==0)
       {
           break;
       }
       v.clear();
       dfs(1,1,"1");
       if(v.size() == 0)
       {
          cout<<"cheat!"<<endl;
       }
       for(int i=0;i<v.size();++i)
       {
           cout<<v[i]<<endl;
       }
    }
}

這題可以只遞迴一次，建表，後面查表。

這題可以只遞迴一次，建表，後面查表。

 

#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
vector <string> v[401];
int n;
void dfs(int cur_sum,int k,string s)
{
    string temp;
    if(cur_sum>400)
    {
        return;
    }
    v[cur_sum].push_back(s);

    temp = s + " + " + to_string(k+1);
    dfs(cur_sum+k+1,k+1,temp);

    temp = s + " * 2";
    dfs(cur_sum*2,k,temp);
}

int main()
{
    cin.sync_with_stdio(false), cin.tie(0);
    for(int i=1;i<=400;++i)
    {
        v[i].clear();
    }
    dfs(0,1,"");
    while(cin>>n)
    {
       if(n==0)
       {
           break;
       }

       if(v[n].size() == 0)
       {
          cout<<"cheat!"<<endl;
       }
       for(int i=0;i<v[n].size();++i)
       {
           cout<<v[n][i]<<endl;
       }
    }
}

只遞迴一次會爆掉
有沒有參考程式碼

string d[401] = {""};

void dv(string v, int rv, int nxt)
{
    if(rv > 400) return;
    d[rv] = d[rv].append(v).append("\n");
    if(rv+nxt <= 400) dv(v + " + " + to_string(nxt), rv+nxt, nxt + 1);
    if(rv*2 <= 400) dv(v + " * 2", rv*2, nxt);
}

dv("1", 1, 2);

string d[401] = {""};

void dv(string v, int rv, int nxt)
{
    if(rv > 400) return;
    d[rv] = d[rv].append(v).append("\n");
    if(rv+nxt <= 400) dv(v + " + " + to_string(nxt), rv+nxt, nxt + 1);
    if(rv*2 <= 400) dv(v + " * 2", rv*2, nxt);
}

dv("1", 1, 2);

 

真的非常謝謝大神指導