samedi 14 décembre 2019

Minimum number of jumps to reach end of the array with sequence using recursion

I have a code for "Minimum number of jumps to reach end of the array with its sequence using recursion". But I am not able to print the sequence.
Any help will be appreciated.

int jump(int arr[], int n, int start, vector<int> &vec)
{
    if(start == n-1)  // base condition
       return 0;

    if( arr[start] == 0)  // if array element is 0 
       return 0;

    vector<int> vec1 = vec;
    vector<int> vec2 = vec;

    int minimum = INT_MAX;
    for( int i = 1 ; i <= arr[start]; i++ )
    {
        vec1.push_back(start);

        int _jump = 1 + jump( arr, n, start+i, vec1);

        vec = (_jump < minimum) ? vec1 : vec2;

        minimum = min(minimum, _jump);
    }
        return minimum;

}

int main()
{
    int arr[] = { 2, 3, 1, 1, 2, 4, 2, 0, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<int> vec;
    cout << jump(arr, n, 0, vec) << endl;

    for( auto x : vec)
        cout << x <<" ";  
    return 0;
}          

output

4      

Expected output

 4       
 0 1 4 5 9

Aucun commentaire:

Enregistrer un commentaire