UVa 10344 - 23 out of 5

UVa Problem

You have five numbers (a0 ... a4) as input and you're required to determine if there's an arrangment of the numbers and operators (+, -, *) that can give a total value of "23"

the expression must be of the form  ( ( ( a0 o a1) o a2)  o a3) o a4
every "o" can be replaced by any of the above operators "+, -, *" and you can use any permutation of the numbers (order is not required).

Solution:

I solved the problem using recursion and backtracking

#include <iostream>
#include <algorithm>

using namespace std;

bool isReachable(int *numbers, bool *used,
      int numsTotal, int numsAvailable, int valExpr)
{
   if(numsAvailable <= 0)
      return false;
   if(numsAvailable == 1)
   {
      for(int i = 0; i < numsTotal; ++i)
      {
         if(!used[i])
            return valExpr == numbers[i];
      }
      return false;
   }

   for(int i = 0; i < numsTotal; ++i)
   {
      if(!used[i])
      {
         int currNum = numbers[i];
         used[i] = true;

         if(isReachable(numbers, used, numsTotal,
               numsAvailable - 1, valExpr - currNum))
         {
            return true;
         }

         if(isReachable(numbers, used, numsTotal,
               numsAvailable - 1, valExpr + currNum))
         {
            return true;
         }

         if(currNum == 0 && valExpr == 0)
            return true;
         if((currNum != 0) && (valExpr%currNum == 0) &&
               isReachable(numbers, used,
                     numsTotal, numsAvailable - 1,
                     valExpr / currNum))
         {
            return true;
         }
         used[i] = false;
      }
   }
   return false;
}

int main(int argc, char *argv[])
{
   const int finalValue = 23;
   const int arrSize = 5;

   int arrNums[arrSize];
   bool used[arrSize];

   while(cin >> arrNums[0])
   {
      bool exit = (arrNums[0] == 0);

      for(int i = 1; i < arrSize; ++i)
      {
         cin >> arrNums[i];
         if(arrNums[i] != 0)
            exit = false;
      }
      if(exit)
         break;

      for(int i = 0; i < arrSize; ++i)
      {
         used[i] = false;
      }

      if(isReachable(arrNums, used, arrSize,
            arrSize, finalValue))
         cout << "Possible" << endl;
      else
         cout << "Impossible" << endl;

   }
   return 0;
}