// StepsByRecursion.cpp
// a recursive program to solve Steps problem
// wdg 2008
#import <iostream>
using namespace std;

  static const int IMPOSSIBLE=-1;
  
  // @pre: required>=0
  // @returns: minimum number of steps; a value of -1 means impossible
  int minSteps(int required, int allowed[], int numAllowed) {
    if(required==0)
       return 0;
    else {
       int min = required+1; //guaranteed to be too large 
       // consider all valid first steps
       for(int poss=0; poss<numAllowed; poss++) 
          if( allowed[poss]<=required ) {
            // call recursively to determine best way to do remainder
            int temp = minSteps( required-allowed[poss], allowed, numAllowed);
            if(temp<min && temp!=IMPOSSIBLE)
               min=temp;
          }
      // return
      if(min==required+1)
        return IMPOSSIBLE;
      else
        return 1+min; 
    }//else
  }

  int main( )
  {
     int coins[] = {1,5,10};     
     cout << "USCoins do 17 in " << minSteps(17,coins,3) << endl; 
           // dime, nickel and 2 pennies
     int silly[] = {2,4,6};
     cout << "Impossible coins returns " << minSteps(17,silly,3) << endl; 
          // odd is impossible
  }