We are provided an array of N numbers and a target value k. We need to find all possible ways to form an expression by inserting the operators ( ,- and *) in such a way that the expression evaluates to the value k.
For example:

• Input: Array = {3,4,3}, k = 15
• Output: 3*4 3, 3 4*3

I couldn't develop a recursive solution to this problem. With just ' ' and '-' operator, it would be easier but because of '*' operator it becomes difficult to use recursive approach as we also need to care about the precendency of operators. Can you help me finding a suitable approach to solve this problem?

CodePudding user response：

Took me while to code this. So it's basically brute force. I recursively (backtracking) generate all possible expression with the operators given and then evaluate them. Note these are just infix expression(s).

Now this is a very slow solution. There are several optimization one can do here.

vector<string> allCombinations(vector<int> &arr, int k)
{
    int n = (int)arr.size();
    string operators = " -*";
    vector<string> ans;
    // To check precedence of operators
    auto prec = [&](char op) -> int
    {
        if (op == '*' or op == '/') return 2;
        if (op == ' ' or op == '-') return 1;
        return -1;
    };
    // For infix evaluation (kindof a helper function)
    auto compute = [&](int v1, char op, int v2) -> int
    {
        if (op == ' ') return v1   v2;
        if (op == '-') return v1 - v2;
        if (op == '*') return v1 * v2;
        if (op == '/') return v1 / v2;
        assert(false);
        return INT_MAX;
    };
    // Main infix evaluation function
    auto evaluate = [&](string s) -> int
    {
        int len = (int)s.size();
        // vector is being used as a STACK
        vector<int> val;
        vector<char> ops;
        for (int i = 0; i < len; i  )
        {
            char curr = s[i];
            if (curr == ' ') continue;
            if (isdigit(curr))
            {
                int v = 0;
                while (i < len and isdigit(s[i])) v = 10 * v   (s[i  ] - '0');
                val.push_back(v);
                i--;
            }
            else
            {
                while (!ops.empty() and prec(curr) <= prec(ops.back()))
                {
                    int v1 = val.back();
                    val.pop_back();
                    int v2 = val.back();
                    val.pop_back();
                    char op = ops.back();
                    ops.pop_back();
                    val.push_back(compute(v2, op, v1));
                }
                ops.push_back(curr);
            }
        }
        while (!ops.empty())
        {
            int v1 = val.back();
            val.pop_back();
            int v2 = val.back();
            val.pop_back();
            char op = ops.back();
            ops.pop_back();
            val.push_back(compute(v2, op, v1));
        }
        return val.back();
    };
    // Generates all expression possible
    function<void(int, string&)> generate = [&](int i, string &s) -> void
    {
        s  = to_string(arr[i]);
        if (i == n - 1)
        {
            if (evaluate(s) == k) ans.push_back(s);
            // Backtrack
            s.pop_back();
            return;
        }
        for (char &ops : operators) 
        {
            s.push_back(ops);
            generate(i   1, s);
            // Backtrack
            s.pop_back();
        }
        // Backtrack
        s.pop_back();
    };
    string s;
    // Try all combinations
    sort(arr.begin(), arr.end());
    do
    {
        generate(0, s);
    } while (next_permutation(arr.begin(), arr.end()));
    return ans;
}

CodePudding user response：

Finding all combinations of operators is pretty simple. If you represent each operator as a digit of a zero-prefixed number in base-3, then you can create a function that renders that base-3 number from an integer, but uses {' ','-','*'} instead of {'0','1','2'} for the digits.

private static final char[] CHARS = " -*".toCharArray();
private char[] generateOperators(int i, int length){
    char[] ops=new char[length];
    for (int x=0; x<length; x  ) ops[x]=CHARS[0];
    for (int x=0; x<length; x  ) {
        ops[length-1-x]=CHARS[i % CHARS.length];
        i /= CHARS.length;
    }
    return ops;
}

You can accumulate your total left to right without backtracking. Keep a total and a separate accumulator. Any time your next operand is a ' ' or '-', it's safe to push your accumulated value to the total. If it's a '*', then you know the current operand is participating in the next accumulation. In this function, I essentially treat every run of multiplied operands as a cluster, treating even single values as a cluster of one, and push that accumulated value to the total when I reach the end of a cluster.

public int evaluate(int[] operands, char[] operators) {
    int sum=0;
    int multiplier=1;
    for (int i=0; i<operators.length; i  ) {
        int operand=operands[i];
        multiplier*=operand;
        if (operators[i]!='*') {
            sum =multiplier;
            multiplier=operators[i]=='-' ? -1 : 1;
        }
    }
    if (operators[operators.length-1]=='*') {
        multiplier*=operands[operands.length-1];
    } else {
        multiplier=(operators[operators.length-1]=='-' ? -1 : 1) * operands[operands.length-1];
    }
    sum =multiplier;
    return sum;
}