Finding target number with given numbers using arithmetic operations

  algorithm, brute-force, c++

I coded a program in C++, it tries to get target value with given numbers using arithmetic operations.
Most of the time, there are several solutions.
Finding one of them is enough. For example, target number is:410 and given numbers are:2,3,5,20,44,50
My program should find a solution like the following:(2*5)*(44-3)

However, my program is adding parentheses to the left-most expression only.
My program only finds solutions like the following: (((((2+3)+5)*44)+20)-50)
Therefore, sometimes my program can’t find solutions although there is a solution.
How should I change my algorithm?

Here is my code:

    #include <iostream>
    #include <string>
    
    int TargetNumber = 410;
    int Numbers[6] = {2,3,5,20,44,50};
    bool isNumberUsed[6] = { 0,0,0,0,0,0 };
    bool isSolutionFound = 0, isOperationUsed = 0;
    std::string answer = "";
    int result;
    
    int calculate(int x, char operation, int y) {
                if (operation == '+')
                    return (x + y);
    
                if (operation == '-')
                    return (x - y);
    
                if (operation == '*')
                    return (x * y);
    
                if (operation == '/' && y != 0 && x%y == 0)
                    return (x / y);
            }
    
    
    void searchSolution(int TargetNumber, std::string term, int value)
            {
                if (TargetNumber == value)
                {
                    isSolutionFound = 1;
                    term.erase(0, 1);
                    term.erase(term.length() - 1, 1);
                    answer = term;
                    return;
                }
    
                for (int a = 0; a < 6; a++)
                {
                    for (int b = 0; b < 4; b++)
                    {
                        isOperationUsed = 0;
                        if (isNumberUsed[a] == 1)
                        {
                            isNumberUsed[a] = 0;
                            if (b == 0)
                            {
                                result = calculate(value, '+', Numbers[a]);
                                isOperationUsed = 1;
                            }
                            if (b == 1)
                            {
                                result = calculate(value, '-', Numbers[a]);
                                isOperationUsed = 1;
                            }
                            if (b == 2)
                            {
                                result = calculate(value, '*', Numbers[a]);
                                isOperationUsed = 1;
                            }
                            if (b == 3 && (value % Numbers[a] == 0) && Numbers[a] != 0)
                            {
                                result = calculate(value, '/', Numbers[a]);
                                isOperationUsed = 1;
                            }
                            if (isOperationUsed == 1 && isSolutionFound == 0)
                            {
                                if (b == 0)
                                    searchSolution(TargetNumber, "(" + term + "+" + std::to_string(Numbers[a]) + ")", result);
                                if (b == 1)
                                    searchSolution(TargetNumber, "(" + term + "-" + std::to_string(Numbers[a]) + ")", result);
                                if (b == 2)
                                    searchSolution(TargetNumber, "(" + term + "*" + std::to_string(Numbers[a]) + ")", result);
                                if (b == 3)
                                    searchSolution(TargetNumber, "(" + term + "/" + std::to_string(Numbers[a]) + ")", result);
                            }
                            isNumberUsed[a] = 1;
                        }
                    }
                }
            }

int main()
{
    for (int c = 0; c < 6; c++)
                {
                    isNumberUsed[c] = 0;
                    searchSolution(TargetNumber, std::to_string(Numbers[c]), Numbers[c]);
                    isNumberUsed[c] = 1;
                }
    
    
                cout << "Solution is:" << answer;
return 0;
}

Source: Windows Questions C++

LEAVE A COMMENT