CareerCup

My solution recursively tries out all operators on the target number and each number in the array. The base case is when the target number equals the last number of the array.

bool validEq(vector<int> arr, float target_num, int i)
{
    if(arr[i]==fabs(target_num) && i==arr.size()-1)
        return true;
    if(i>=arr.size())
        return false;
        
    return (validEq(arr, target_num+arr[i], i+1) || validEq(arr, target_num-arr[i], i+1) ||
        validEq(arr, target_num*arr[i], i+1) || validEq(arr, (float)target_num/arr[i], i+1));
}

In gist:
1. Create a combination of operators that is array of numbers length long.
2. Interleave it with the elements of the array of numbers to create an expression.
3. Create postfix expression.
4. Evaluate the expression and report back if it matches;

The idea here is to generate combinations of the operators as long as the length of the array ( identified by k here).

Once you generate a combination, prune the invalid operator combinations defined as the combination that either start with '*' or '/' .

If the combination of the operator starts with either + or - , simply prefix 0 to it and it will be a valid expression.

Next is a trivial case of converting it into postfix and evaluating the postfix ( code not shown here). After evaluating the postfix expression, compare if the result is the same as desired. If so, print it after removing the 0 that we had added prior.

void createExpressions(char expr[],int expr_n,int k,int numElements,int start,char branches[],int a[],int a_n,int sum) {
	if(numElements==k) {
		if(branches[0]=='*' || branches[0]=='/') return;
		string op;
		if(branches[0]=='-' || branches[0]=='+') {
			op=op+'0'+branches[0];
		}
		int i=1;
		while(i<numElements) {
			op=op+(char)(a[i-1]+'0')+branches[i];
			i++;
		}
		op=op+(char)(a[i-1]+'0');
		string postfixed=postfix(op);
		int result=evaluatePostfix(postfixed);
		if(result==sum) {
			printf("%s\n",op.substr(2,op.length()-2).c_str());
		}
		fflush(stdout);
		return;
	}
	for(int i=0;i<expr_n;i++) {
		branches[numElements++]=expr[i];
		createExpressions(expr,expr_n,k,numElements,++start,branches,a,a_n,sum);
		numElements--;
	}
}

void createValidExpressionsToSum(char expr[],int expr_n,int a[],int a_n,int sum) {
	char branches[a_n];
	memset(branches,0x00,sizeof(branches));
	createExpressions(expr,expr_n,a_n,0,0,branches,a,a_n,sum);
}

call as :
char expr[]={'+','-','/','*'};
int a[]={5,5,1};
createValidExpressionsToSum(expr,4,a,3,9);

For the first element in the list, solve the problem recursively for each symbol. For +, recursively look for a way to combine all the remaining elements to equal the target minus the current element. For *, recursively look for a way to comine all the elements to equal the target divided by the current element. For -, look for target+x as well x - target.

If pulling out the first element doesn't yield a solution, move on the second, and so on.

Here is my recursive solution in javascript. Complexity is 4^(n-1) because in the worst case we simply generate all possible combinations of – + * /

function eveluate(numbers, N) {
    var remainingNumbers, firstNumber, secondNumber;

    if (numbers.length === 0) {
        return false;
    } else if (numbers.length === 1) {
        return Math.abs(numbers[0] - N) < 0.00001;
    } else {
        remainingNumbers = numbers.slice(1);

        firstNumber = numbers[0];
        secondNumber = remainingNumbers[0];

        if (eveluate(remainingNumbers, N - firstNumber))  {
            return true;
        } else {
            remainingNumbers[0] = - secondNumber;

            if (eveluate(remainingNumbers, N - firstNumber)) {
                return true;
            } else {
                remainingNumbers[0] = firstNumber * secondNumber;

                if (eveluate(remainingNumbers, N)) {
                    return true;
                } else {
                    remainingNumbers[0] = firstNumber / secondNumber;

                    if (eveluate(remainingNumbers, N)) {
                        return true;
                    }
                }
            }
        }
    }
}

I think we need to consider the last number as well for * and / operations. And do the needful to get the right total. Here is how i would solve it

public String findExpression ( int N, int sum, String current, int [ ] numbers, int lastNumber ) {
	
	if ((current.length()+1)/2 == number.length) {	
			if (sum == N)	
				return current;
			return null;
		}

	
	for (int i=0; i<number.length; i++) {
		
		if (current.length() == 0) {
			current += number[i];
			sum = number[i];
			exp = findExpression (N, sum, current, number, number[i]);
		} else {
			String exp = null;
			// addition
			current += "+"+number[i];
			sum += number[i];
			exp = findExpression (N, sum, current, number, number[i]));
			if (exp != null) return exp;

			//subtraction
			current += "-"+number[i];
			sum -= number[i];
			exp = findExpression (N, sum, current, number, number[i]));
			if (exp != null) return exp;

			//multiplication 
			current += "*"+number[i];
			sum +=lastNumber * number[i] - lastNumber;
			exp = findExpression (N, sum, current, number, lastNumber*number[i]));
			if (exp != null) return exp;

			//division
			current += "/"+number[i];
			sum +=lastNumber / number[i] - lastNumber;
			exp = findExpression (N, sum, current, number, lastNumber/number[i]));
		}
		
		if (exp != null) return exp;
	}
	return null;
}

static char symbols[] = {'+', '-', '*', '/'};
static float getSum(float test[], float ans, int operators[], int count)
{
        float prev, result = 0.0;
        int i;
        for (i = 0; i < count; ++i)
        {
            if (0 == operators[i])
            {
                prev = test[i];
                result += prev;
            }
            else if (1 == operators[i])
            {
                prev = -test[i];
                result += prev;
            }
            else if (2 == operators[i]) // multiplication
            {
                result -= prev;
                prev = prev*test[i];
                result += prev;
            }
            else // division
            {
                result -= prev;
                prev = prev/test[i];
                result += prev;
            }
        }
        return result;
}

static void findAnswerRecur(float test[], float ans, int len, int operators[], int count)
{
    float result = 0.0;
    int i;
    if (count == len)
    {
        float result = getSum(test, ans, operators, count);
        if (ans == result)
        {
            for (i = 0; i < len; ++i)
                printf("%c %.0f ", symbols[operators[i]], test[i]);
            printf(" = %.2f\n", ans);
        }
        return;
    }

    for  (i = 0; i < 4; ++i)
    {
        operators[count] = i;
        findAnswerRecur(test, ans, len, operators, count+1);
    }
 }


static void findAnswer(float test[], float ans, int len)
{
    int operators[4];
    int count = 0;
    int i;
    // only apply +/- at the very first
    for (i = 0; i < 2; ++i)
    {
        operators[count] = i;
        findAnswerRecur(test, ans, len, operators, count+1);
    }
}

C solution using combinatorial method:

static char symbols[] = {'+', '-', '*', '/'};
static float getSum(float test[], float ans, int operators[], int count)
{
        float prev, result = 0.0;
        int i;
        for (i = 0; i < count; ++i)
        {
            if (0 == operators[i])
            {
                prev = test[i];
                result += prev;
            }
            else if (1 == operators[i])
            {
                prev = -test[i];
                result += prev;
            }
            else if (2 == operators[i]) // multiplication
            {
                result -= prev;
                prev = prev*test[i];
                result += prev;
            }
            else // division
            {
                result -= prev;
                prev = prev/test[i];
                result += prev;
            }
        }
        return result;
}

static void findAnswerRecur(float test[], float ans, int len, int operators[], int count)
{
    float result = 0.0;
    int i;
    if (count == len)
    {
        float result = getSum(test, ans, operators, count);
        if (ans == result)
        {
            for (i = 0; i < len; ++i)
                printf("%c %.0f ", symbols[operators[i]], test[i]);
            printf(" = %.2f\n", ans);
        }
        return;
    }

    for  (i = 0; i < 4; ++i)
    {
        operators[count] = i;
        findAnswerRecur(test, ans, len, operators, count+1);
    }
 }


static void findAnswer(float test[], float ans, int len)
{
    int operators[4];
    int count = 0;
    int i;
    // only apply +/- at the very first
    for (i = 0; i < 2; ++i)
    {
        operators[count] = i;
        findAnswerRecur(test, ans, len, operators, count+1);
    }
}

char op[]={'+','-','*','/'};
bool eval(int a[],int target,int n,int pos,int prev)
{
	if(pos == n) {
		if(prev == target)	{
            return true;
		}
		return false;
	}
	for(int i=0;i<4;i++) {
		int res = 0;
		char ch = op[i];
		if(ch == '+') {
			res = prev + a[pos];
		} else if(ch == '-') {
			res = prev - a[pos];
		} else if(ch == '*') {
			res = prev * a[pos];
		} else {
			res = prev / a[pos];
		}
		if(	eval(a,target,n,pos+1,res ) )
			return true;
	}
	return false;
}

char op[]={'+','-','*','/'};
bool eval(int a[],int target,int n,int pos,int prev)
{
	if(pos == n) {
		if(prev == target)	{
            return true;
		}
		return false;
	}
	for(int i=0;i<4;i++) {
		int res = 0;
		char ch = op[i];
		if(ch == '+') {
			res = prev + a[pos];
		} else if(ch == '-') {
			res = prev - a[pos];
		} else if(ch == '*') {
			res = prev * a[pos];
		} else {
			res = prev / a[pos];
		}
		if(	eval(a,target,n,pos+1,res ) )
			return true;
	}
	return false;
}

I constructed an expression tree recursively. It works well. If there is n numbers and 4 operators, then the time should be O(4^n*n!), and the space is O(n^2) (mainly used in stack when doing recursion).

#include <vector>
#include <iostream>
#include <iterator>

using namespace std;

enum Op {ADD, MUL, SUB, DIV};

class Node {
public:
  Node *left, *right;
  int value;
  Op op;
  Node (int value) : value(value) { left = right = NULL; }
  bool setChild (Node *left, Node *right, Op op) {
    this->left = left;
    this->right = right;
    this->op = op;
    switch (op) {
    case ADD:
      this->value = left->value + right->value;
      break;
    case SUB:
      this->value = left->value - right->value;
      break;
    case MUL:
      this->value = left->value * right->value;
      break;
    case DIV:
      if (right->value == 0 || (left-value % right->value != 0))
	return false;
      this->value = left->value / right->value;
      break;
    }
    return true;
  }
  void print() {
    cout << left->value;
    switch(op) {
    case ADD:
      cout << " + ";
      break;
    case SUB:
      cout << " - ";
      break;
    case MUL:
      cout << " * ";
      break;
    case DIV:
      cout << " / ";
      break;
    }
    cout << right->value << endl;
  }
};

Node *constructExpressionTree(vector<Node*> &nodes, int target) {
  if (nodes.size() == 1 && nodes[0]->value == target) {
    return nodes[0];
  }
  int size = nodes.size();
  Node *new_node = new Node(0), *result = NULL;
  bool valid;
  vector<Node*> next_nodes;
  for (int i = 0; i < size && !result; ++i) {
    for (int j = i + 1; j < size && !result; ++j) {
      next_nodes.clear();
      next_nodes.insert(next_nodes.end(), nodes.begin(), nodes.begin() + i);
      next_nodes.insert(next_nodes.end(), nodes.begin() + i + 1, nodes.begin() + j);
      next_nodes.insert(next_nodes.end(), nodes.begin() + j + 1, nodes.end());
      next_nodes.push_back(new_node);

      for (int op = ADD; op <= DIV; ++op) {
	valid = new_node->setChild(nodes[i], nodes[j], static_cast<Op>(op));
	if (valid && (result = constructExpressionTree(next_nodes, target))) {
	  new_node->print();
	  break;
	}
	if (op >= SUB) {
	  valid = new_node->setChild(nodes[j], nodes[i], static_cast<Op>(op));
	  if (valid && (result = constructExpressionTree(next_nodes, target))) {
	    new_node->print();
	    break;
	  }
	}
      }
    }
  }
  if (!result)
    delete new_node;
  return result;
}

Node *construct(vector<int> numbers, int target) {
  vector<Node*> expression;
  for (vector<int>::iterator it = numbers.begin();
       it != numbers.end(); ++it) {
    Node *node = new Node(*it);
    expression.push_back(node);
  }
  return constructExpressionTree(expression, target);
}

void print(Node *root, bool par = false) {
  if (!root) {
    cout << "no valid expression. " << endl;
    return;
  }
  if (root->left && root->right) {
    if (par)
      cout << "(";
    bool left_par = (root->op == MUL || root->op == DIV) &&
      (root->left->op == ADD || root->left->op == SUB);
    bool right_par = root->op == DIV || 
      ((root->op == MUL || root->op == SUB) && 
       (root->right->op == ADD || root->right->op == SUB));
    print(root->left, left_par);
    switch(root->op) {
    case ADD:
      cout << " + ";
      break;
    case SUB:
      cout << " - ";
      break;
    case MUL:
      cout << " * ";
      break;
    case DIV:
      cout << " / ";
      break;
    }
    print(root->right, right_par);
    if (par)
      cout << ")";
  } else {
    cout << root->value;
  }
}

void deleteNodes(Node *root) {
  if (!root)
    return;
  deleteNodes(root->left);
  deleteNodes(root->right);
  delete root;
}

int main() {
  vector<int> numbers;
  int target = 24;
  srand((unsigned)time(NULL));
  numbers.push_back(rand() % 13 + 1);
  numbers.push_back(rand() % 13 + 1);
  numbers.push_back(rand() % 13 + 1);
  numbers.push_back(rand() % 13 + 1);
  copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  Node *root = construct(numbers, target);
  print(root);
  cout << endl;
  deleteNodes(root);
}