仅由长度为 1 到 10 的两个字母生成所有字符串？

Question

我想生成长度从 1 到 10 的所有字符串，仅由单词“4”和“7”按排序顺序排列

  example-> 1)4 //first string

            2)7 //second string

            3)44 //third,because next after 7 should be 44

            4)47 //fourth,after 44

            . . .

            . . .

            . . .

            This way till length <=10

我自己试了一下，我的回溯代码看起来像这样

        #include<bits/stdc++.h>
        using namespace std;
        vector<string>v;                // for storing intermediate string in backtracking
        void generate(string s,char ch)
        {
            if(s.length()>=9)return;    //length > 10 returning
            s+=ch;                      //adding to string a new character
            v.push_back(s);                    //storing strings
            generate(s,'4');            //first backtracking
            generate(s,'7');            //second backtracking
        }
        int main()
        {
        generate("",'4');
        sort(v.begin(),v.end());     //sorting  to get ascending order string
        string thisfind;             //to find postion of string thisfind in vector...like postion of '4' is 1
        cin>>thisfind;
        int l=find(v.begin(),v.end(),thisfind)-v.begin();  //just usual find function
        cout<<l+1<<endl;            //output
        return 0;
    }

这是不正确的，请提出一个回溯算法来做同样的事情

注意：- 不用担心时间复杂度

Answer 1

不需要回溯，因为存在一个非常简单的算法，它总是做正确的事情：

从空字开始。（因为你需要长度> 0，所以不需要打印）
完成尺寸 n - 1 的工作后，您可以通过以下方式完成尺寸 n 的工作：
- 打印每个大小为 n - 1 并带有“4”前缀的单词
- 然后打印大小为 n - 1 的每个单词，前缀为“7”

因为你所做的每一步都保证朝着正确的方向移动（即使在实际上没有明确存储任何东西的递归实现中），这并不是真正的回溯 - 但你为什么要回溯呢？

P.S.: 这个算法是最优的：它为它打印的每个字符花费 O(1) 时间。

Answer 2

我正在写我自己的答案 question.I 在投入一些时间后找到了解决方案。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long int
vector<ll> v;
void recurse(ll num)
{
    v.push_back(num);
    if (num > ((ll)10e10))
        return;
    recurse(num * 10 + 4);
    recurse(num * 10 + 7);
}

int main()
{
    recurse(0);
    sort(v.begin(), v.end());
    ll n;
    cin >> n;
    cout << find(v.begin(),v.end(),n)-v.begin()<< endl;
    return 0;
}

已经提出了更好的算法，但我虽然分享这个会很好。

仅由长度为 1 到 10 的两个字母生成所有字符串？

Generating all strings by only two letters having length from 1 to 10?

c++

string

recursion

recursive-backtracking