c++ (permutation + dfs + enumeration)


  • 0
    Z
    class Solution {
    public:
        bool judgePoint24(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            bool res = false;
            do {
                if (dfs(nums, 0)) return true;
            } while (next_permutation(nums.begin(), nums.end()));
            return false;
        }
        bool dfs(vector<int>& a, int pos) {
            if (pos == 3) {
                bool res = 
                    (C(C(C(a[0], o[0], a[1]), o[1], a[2]), o[2], a[3]) == 24) ||
                    (C(C(a[0], o[0], a[1]), o[1], C(a[2], o[2], a[3])) == 24) ||
                    (C(C(a[0], o[1], C(a[1], o[1], a[2])), o[2], a[3]) ==24) ||
                    (C(a[0], o[0], C(C(a[1], o[1], a[2]), o[2], a[3])) == 24) ||
                    (C(a[0], o[0], C(a[1], o[1], C(a[2], o[2], a[3]))) == 24);
                
                return res;
            }
            for (int i = 0; i < 4; i++) {
                o.push_back(op[i]);
                if (dfs(a, pos + 1)) return true;
                o.pop_back();
            }
            return false;
        }
        double C(double a, char op, double b) {
            if (op == '+') return a + b;
            else if (op == '-') return a - b;
            else if (op == '*') return a * b;
            else {
                if (b == 0) return 0x3ffffff;
                return a / b;
            }
        }
    private:
        string op = "+-*/";
        string o = "";
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.