Binglong's space

#include <memory>           // std::unique_ptr
#include <optional>         // std::optional
#include <utility>          // std::move
#include <vector>           // std::vector
#include <variant>          // std::variant
#include <cassert>          // assert
#include <iostream>


enum class Operator {
    Add,
    Subtract,
    Multiply,
    Divide
};

struct Expression;

inline void printIndent(std::ostream& os, int indent) {
    for(int i=0; i<indent; ++i) {
        os << "  ";
    }
}

std::ostream& operator<<(std::ostream& os, Operator op) {
    switch(op){
        case Operator::Add:         os << "+"; break;
        case Operator::Subtract:    os << "-"; break;
        case Operator::Multiply:    os << "*"; break;
        case Operator::Divide:      os << "/"; break;
        default:                    assert(false); break;
    }
    return os;
}

struct BinaryExpression {
    std::unique_ptr<Expression> left;
    Operator                    op;
    std::unique_ptr<Expression> right;
    
    BinaryExpression(BinaryExpression&&) = default;
    BinaryExpression(std::unique_ptr<Expression> left, Operator op, std::unique_ptr<Expression> right);
    BinaryExpression clone() const;
    std::optional<int> evaluate() const;
    friend std::ostream& operator<< (std::ostream& os, const BinaryExpression& v);
};

struct Expression {
    std::variant<int, BinaryExpression> expr;   // terminal or binary expression
    
    Expression(BinaryExpression binaryExpr) : expr(std::move(binaryExpr)) {}
    Expression(int terminal) : expr(terminal) {}
    
    std::unique_ptr<Expression> clone() const {
        if( std::holds_alternative<int>(expr) ) {
            return std::make_unique<Expression>(std::get<int>(expr));
        }
        else {
            return std::make_unique<Expression>(std::get<BinaryExpression>(expr).clone());
        }
    }
    
    std::optional<int> evaluate() const {
        return std::holds_alternative<int>(expr) ?
        std::optional{std::get<int>(expr)} : std::get<BinaryExpression>(expr).evaluate();
    }
    
    friend std::ostream& operator<< (std::ostream& os, const Expression& v) {
        return std::holds_alternative<int>(v.expr)? (os << std::get<int>(v.expr)) : (os << std::get<BinaryExpression>(v.expr) );
    }
};

BinaryExpression::BinaryExpression(std::unique_ptr<Expression> left, Operator op, std::unique_ptr<Expression> right)
: left(std::move(left)), op(op), right(std::move(right)) {
}

BinaryExpression BinaryExpression::clone() const {
    return BinaryExpression{ left->clone(), op, right->clone() };
}

std::optional<int> BinaryExpression::evaluate() const {
    auto a = left->evaluate();
    auto b = right->evaluate();
    if( !a || !b ) {
        return {};          // error
    }
    switch(op) {
        case Operator::Add:         return (*a) + (*b);
        case Operator::Subtract:    return (*a) - (*b);
        case Operator::Multiply:    return (*a) * (*b);
        case Operator::Divide: {
            if( (*b) == 0 ) {
                return {};  // divided by 0
            }
            else if( (*a) % (*b) != 0 ) {
                return {};  // has remainder
            }
            else {
                return (*a) / (*b); // good
            }
        }
        default:
            assert(false);  // should not be here.
            return {};
    }
}

std::ostream& operator<< (std::ostream& os, const BinaryExpression& v) {
    return os << "(" << *v.left << v.op << *v.right << ")";
}


std::optional<std::unique_ptr<Expression>> get_expression_for_target(const std::vector<std::unique_ptr<Expression>>& expressions, int target);

// add `ab` to end of `others` and try to shoot target
// if failure, return empty, and restore `others` (for next try later)
// if success, return the valid expression that evaluates to `target`
std::optional<std::unique_ptr<Expression>> get_expression_for_target(std::unique_ptr<Expression> ab, std::vector<std::unique_ptr<Expression>>& others, int target) {
    others.push_back( std::move(ab) );
    if(auto result = get_expression_for_target(others, target)) {
        return result;
    }
    // did not work: revert `others`.
    others.pop_back();
    return {};
}

// try to construct an expression using members in `expressions` exactly once with operators (+,-,*,/) to evaluate to `target`
// if failure, return empty.
// if success, return the valid expression that evaluates to `target`
std::optional<std::unique_ptr<Expression>> get_expression_for_target(const std::vector<std::unique_ptr<Expression>>& expressions, int target) {
    if( expressions.size()==0u ) {
        return {};  // no way
    }
    
    // base case
    if( expressions.size()==1u ) {
        if( auto value = expressions.front()->evaluate(); value && *value == target ) {
            return expressions.front()->clone();
        }
        else {
            return {};  // no result
        }
    }
    
    // reduce to a size-1 problem by combining 2 arbitrary expressions
    for(size_t i=0; i<expressions.size()-1u; ++i) {
        for(size_t j=i+1; j<expressions.size(); ++j) {
            auto& a = expressions[i];
            auto& b = expressions[j];
            
            std::vector<std::unique_ptr<Expression>> others;
            for(size_t k=0; k<expressions.size(); ++k) {
                if( k!=i && k!=j) {
                    others.push_back(expressions[k]->clone());
                }
            }
            
            // a + b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Add, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // a - b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Subtract, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // b - a
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(b->clone(), Operator::Subtract, a->clone())),
                                                       others, target)) {
                return result;
            }
            
            // a * b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Multiply, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // a / b
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(a->clone(), Operator::Divide, b->clone())),
                                                       others, target)) {
                return result;
            }
            
            // b / a
            if(auto result = get_expression_for_target(std::make_unique<Expression>(BinaryExpression(b->clone(), Operator::Divide, a->clone())),
                                                       others, target)) {
                return result;
            }
        }
    }
    return {};  // no result
}

std::vector<std::unique_ptr<Expression>> create_expressions(const std::vector<int>& numbers) {
    std::vector<std::unique_ptr<Expression>> expressions;
    for(auto number : numbers) {
        expressions.push_back(std::make_unique<Expression>(number));
    }
    return expressions;
}

void test(int target, const std::vector<int>& numbers) {
    
    std::cout << "Trying to get " << target << " from: ";
    for(auto number : numbers) {
        std::cout << number << " ";
    }
    
    if( auto expr = get_expression_for_target(create_expressions(numbers), target) ) {
        std::cout << "  Success: " << (**expr) << "\n";
    }
    else {
        std::cout << "  Failure: No result\n";
    }
}


int main() {
    test(24, std::vector<int>{1,1,1,1,1});
    test(24, std::vector<int>{2,2,2,2,2});
    test(24, std::vector<int>{3,3,3,3,3});
    test(24, std::vector<int>{4,4,4,4,4});
    test(24, std::vector<int>{5,5,5,5,5});
    test(24, std::vector<int>{6,6,6,6,6});
    test(24, std::vector<int>{7,7,7,7,7});
    test(24, std::vector<int>{8,8,8,8,8});
    test(24, std::vector<int>{9,9,9,9,9});
    return 0;
}

Trying to get 24 from: 1 1 1 1 1   Failure: No result
Trying to get 24 from: 2 2 2 2 2   Success: ((2+2)*(2+(2+2)))
Trying to get 24 from: 3 3 3 3 3   Success: ((3+3)+(3*(3+3)))
Trying to get 24 from: 4 4 4 4 4   Success: ((4*(4+4))-(4+4))
Trying to get 24 from: 5 5 5 5 5   Success: (((5*(5*5))-5)/5)
Trying to get 24 from: 6 6 6 6 6   Success: ((6+6)*((6+6)/6))
Trying to get 24 from: 7 7 7 7 7   Failure: No result
Trying to get 24 from: 8 8 8 8 8   Success: ((8+8)-(8-(8+8)))
Trying to get 24 from: 9 9 9 9 9   Failure: No result