//Even though this was in a Mock. Gos the result in Geeks. Questão dificil do kct. :)
class Solution {
// Utility recursive method to generate all possible
// expressions
void getExprUtil(vector<string>& res, string curExp,
                 string input, int target, int pos,
                 int curVal, int last)
{
    // true if whole input is processed with some
    // operators
    if (pos == input.length())
    {
        // if current value is equal to target
        //then only add to final solution
        // if question is : all possible o/p then just
        //push_back without condition
        if (curVal == target)
            res.push_back(curExp);
        return;
    }

    // loop to put operator at all positions
    for (int i = pos; i < input.length(); i++)
    {
        // ignoring case which start with 0 as they
        // are useless for evaluation
        if (i != pos && input[pos] == '0')
            break;

        // take part of input from pos to i
        string part = input.substr(pos, i + 1 - pos);

        // take numeric value of part
        int cur = atoi(part.c_str());

        // if pos is 0 then just send numeric value
        // for next recurion
        if (pos == 0)
            getExprUtil(res, curExp + part, input,
                     target, i + 1, cur, cur);


        // try all given binary operator for evaluation
        else
        {
            getExprUtil(res, curExp + "+" + part, input,
                     target, i + 1, curVal + cur, cur);
            getExprUtil(res, curExp + "-" + part, input,
                     target, i + 1, curVal - cur, -cur);
            getExprUtil(res, curExp + "*" + part, input,
                     target, i + 1, curVal - last + last * cur,
                     last * cur);
        }
    }
}

public:
    // Below method returns all possible expression
    // evaluating to target
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        getExprUtil(res, "", num, target, 0, 0, 0);
        return res;
    }
};