递归函数 - 子序列

Question

我正在尝试获得一个递归函数，它应该比较两个 int 数组并判断 array2 是否是 array1 的子序列。我现在的问题是我不知道何时设置 bool 递归函数的 return 值。我很高兴能得到您的帮助。

int array1 [] = {1 ,2 ,3 ,4 ,5 ,6,7,8,9,10};
int array2 [] = {2,4,6,8};
int l1 = 10;
int l2 = 4;


bool isSubset ( int p1 , int p2) {

   while (p1 <= l1) {
       if (array1[p1] == array2[p2]) {
            isSubset(p1 + 1, p2 + 1);
        } else {
            isSubset(p1 + 1, p2);
        }
    }
}


int main (void) {
    if ( isSubset(0,0))
        cout << "yes" << endl ;
    else
        cout << " no " << endl ;

    return 0;
}

Answer 1

Return true 如果您找到了 array2 的所有项目（即如果 p2 == l2）。如果您已经到达 array1 的末尾，但还有一些 array2 的项目您还没有找到，return false.
否则，收集 isSubset 的所有递归调用结果，如果至少有一个 true, return true.
代码：

bool isSubset ( int p1 , int p2) {
    if(p2 >= l2) return true; //  we have found all array2's items
    if(p1 >= l1) return false; 
    bool result = false;

    while (p1 < l1 && !result) { // whether we have found the subsequence - break the loop
        if (array1[p1] == array2[p2]) {
            result |= isSubset(p1 + 1, p2 + 1);
        } else {
            result |= isSubset(p1 + 1, p2);
        }
        ++p1;
    }
    return result; 
}

这里不需要 while 循环，这也可以：

bool isSubset ( int p1 , int p2) {
    if(p2 >= l2) return true; //  we have found all array2's items
    if(p1 >= l1) return false; 
    if(array1[p1] == array2[p2]){
        return isSubset(p1 + 1, p2 + 1);
    }else{
        return isSubset(p1 + 1, p2);
    }
}

或更短：

bool isSubset ( int p1 , int p2) {
    if(p2 >= l2) return true; //  we have found all array2's items
    if(p1 >= l1) return false; 
    return isSubset(p1 + 1 , p2 + (array1[p1] == array2[p2]));
}

p.s。 isSubset 在这种情况下是错误的名称，因为该算法对顺序敏感。

Answer 2

#include<bits/stdc++.h>
using namespace std;

int subs(string input,string output[]){
    if(input.length()==0){
        output[0]="";
        return 1;
    }
    string smallstring=input.substr(1);
    int smallans=subs(smallstring,output);
    for(int i=0;i<smallans;i++){
        output[i+smallans]=input[0]+output[i];
    }
    return 2*smallans;
}

int main(){
    string input;
    cin>>input;
    int len=input.length();
    int osize=pow(2,len);
    string *output=new string[osize];
    
    int count=subs(input,output);
    for(int i=0;i<count;i++){
        cout<<output[i]<<endl;
    }
}

递归函数 - 子序列

recursive function - subsequence

c++

recursion

boolean

subsequence