https://leetcode.com/contest/leetcode-weekly-contest-50/problems/24-game/

[Implementation idea]:

The following 1st implementation passed but NOT efficient. Try to speed up it.

#include <iostream>
#include <limits.h>
#include <vector>
#include <list>
#include <iterator>
#include <queue>
#include <algorithm>

using namespace std;

int gcd(int a, int b)
{
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
}

int lcm(int a, int b)
{
    int temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
}

pair<int, int> mySum(pair<int, int> &a, pair<int, int> &b) {
    //printf("sum (%d %d) (%d %d)\n" , a.first, a.second, b.first, b.second);
    int denum = lcm(a.second, b.second);
    int num   = ((denum / a.second) * (a.first)) + ((denum / b.second) * (b.first));
    //printf("%d/%d\n" , num, denum);
    return make_pair(num, denum);
}

pair<int, int> myPlus(pair<int, int> &a, pair<int, int> &b) {
    //printf("plus (%d %d) (%d %d)\n" , a.first, a.second, b.first, b.second);
    int denum = lcm(a.second, b.second);
    int num   = ((denum / a.second) * (a.first)) - ((denum / b.second) * (b.first));
    //printf("%d/%d\n" , num, denum);
    return make_pair(num, denum);
}

pair<int, int> myMultiply(pair<int, int> &a, pair<int, int> &b) {
    //printf("mul (%d %d) (%d %d)\n" , a.first, a.second, b.first, b.second);
    int denum = a.second * b.second;
    int num   = a.first  * b.first;
    //printf("%d/%d\n" , num, denum);
    return make_pair(num, denum);
}

pair<int, int> myDivide(pair<int, int> &a, pair<int, int> &b) {
    //printf("div (%d %d) (%d %d)\n" , a.first, a.second, b.first, b.second);
    if (b.first == 0)
        return make_pair(0, 0);
    int denum = a.second * b.first;
    int num   = a.first  * b.second;
    //printf("%d/%d\n" , num, denum);
    return make_pair(num, denum);
}

typedef pair<int, int> (*operatorFunct)(pair<int, int> &a, pair<int, int> &b);


void dump(list<pair<int, int>> &input) {
    list<pair<int, int>>::iterator it;
    for (it = input.begin(); it != input.end(); it++) {
        //printf("[%d %d]\n", it->first, it->second);
    }
    //printf("end\n");
}


class Solution {

public:
    bool judgePoint24(vector<int>& nums) {
        typedef pair<int, int> (*op)(pair<int, int> &a, pair<int, int> &b);
        op opArray[4] = {mySum, myPlus, myMultiply, myDivide};

        std::sort (nums.begin(), nums.end());
        do {
            //std::cout << nums[0] << ' ' << nums[1] << ' ' << nums[2] << ' ' << nums[3] <<'\n';
            list<pair<int, int>> numList;
            list<int>            opList;
            queue<int>           operandPair;
            char opSymbol[4] = {'+', '-', '*', '/'};

            /*0: +, 1: -, 2: *, 3: /*/
            for (int o1 = 0; o1 < 4; o1++) {
                for (int o2 = 0; o2 < 4; o2++) {
                    for (int o3 = 0; o3 < 4; o3++) {
                        for (int secondOperand = 0; secondOperand < 2; secondOperand++) {
                            for (int firstOperand = 0; firstOperand < 3; firstOperand++) {
                                operandPair.push(firstOperand);
                                operandPair.push(secondOperand);
                                operandPair.push(0);
                                opList.clear();
                                opList.push_back(o1);
                                opList.push_back(o2);
                                opList.push_back(o3);
                                numList.clear();
                                for (int i = 0; i < nums.size(); i++) {
                                    numList.push_back(make_pair(nums[i], 1));
                                }
                                while (numList.size() > 1) {
                                    int first = operandPair.front();
                                    operandPair.pop();
                                    list<pair<int, int>>::iterator it1 = numList.begin();
                                    list<pair<int, int>>::iterator it2 = numList.begin();
                                    std::advance(it1, first);
                                    std::advance(it2, (first + 1));
                                    list<int>::iterator itOp = opList.begin();
                                    std::advance(itOp, first);

                                    operatorFunct funct = opArray[*(itOp)];
                                    pair<int, int> res = (*funct)((*it1), (*it2));
                                    it2++;
                                    if (res.second == 0) {
                                        while (!operandPair.empty())
                                        {
                                            operandPair.pop();
                                        }
                                        //printf("Illegal (%c %c %c %d %d)\n", opSymbol[o1], opSymbol[o2], opSymbol[o3], firstOperand, secondOperand);
                                        break;
                                    }

                                    numList.erase(it1, it2);
                                    it1 = numList.begin();
                                    if (it1 != numList.end())
                                        std::advance(it1, first);
                                    opList.erase(itOp);
                                    numList.insert(it1, res);
                                }
                                //printf("end\n");
                                if (numList.size() == 1) {
                                    list<pair<int, int>>::iterator it = numList.begin();
                                    if (it->first == (it->second * 24)) {
                                        //std::cout << nums[0] << ' ' << nums[1] << ' ' << nums[2] << ' ' << nums[3] <<'\n';
                                        //printf("Found (%c %c %c %d %d)\n", opSymbol[o1], opSymbol[o2], opSymbol[o3], firstOperand, secondOperand);
                                        return true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        } while (std::next_permutation(nums.begin(), nums.end()));

        return false;
    }
};


int main()
{
    int myints[] = {4, 1, 8, 7};
    pair<int, int> inputPair[] = {make_pair(myints[0], 1), make_pair(myints[1], 1), make_pair(myints[2], 1), make_pair(myints[3], 1)};
    vector<int> input(myints, myints + sizeof(myints) / sizeof(int) );
    vector<pair<int, int>> testInput(inputPair, inputPair + sizeof(inputPair) / sizeof(pair<int, int>) );

    Solution solution;
    bool res = solution.judgePoint24(input);
    printf("res = %d\n", res);

    return 1;
}