c++ - 仅由长度为 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) 时间。