0

I'm trying to get a recursive Function, which should compare two int arrays and say wether array2 is a subsequence of array1. My Problem is now that i dont know when to set the return value of an bool recursive function. I'm glad for every help.

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;
}
Truut
  • 83
  • 1
  • 11

2 Answers2

0

Return true if you have found all items of array2 (that is, if p2 == l2). If you've reach the end of the array1, but there is still some items of array2 that you haven't found yet, return false.
Otherwise, collect all results of recursive calls of isSubset and if there is at least one true, return true.
The code:

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; 
}

And you don't need a while loop here, this will work too:

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);
    }
}

Or even shorter:

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 is bad name in this case because this algorithm is order-sensitive.

Mama Bullki
  • 128
  • 4
0
#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;
    }
}
Ashish Kumar Patel
  • 1