C++ BackTracking


  • 0
    M
    class Solution {
    private:
        vector<int> nums;
        vector<bool> used;
        vector<double> st;
        int used_cnt = 0;
        
        double const c_eps = 0.000001;
        double const c_final = 24;
        
        enum Ops { c_add, c_sub, c_mul, c_div, c_num_ops, };
    public:
        bool Solve() {
            if (st.size() == 1 && fabs(st.back() - c_final) < c_eps && used_cnt == nums.size()) return true;
            if (st.size() >= 2) {
                for (int i = 0; i < c_num_ops; ++i) {
                    double a = st.rbegin()[1], b = st.rbegin()[0];
                    if (i == c_div && b == 0) continue;
                    st.pop_back(); st.pop_back();
                    switch (Ops(i)) {
                        case c_add: st.push_back(a + b); break;
                        case c_sub: st.push_back(a - b); break;
                        case c_mul: st.push_back(a * b); break;
                        case c_div: st.push_back(a / b); break;
                    }
                    if (Solve()) return true;
                    st.pop_back();
                    st.push_back(a); st.push_back(b);
                }
            }
            for (int i = 0; i < nums.size(); ++i) {
                if (used[i]) continue;
                used[i] = true; ++used_cnt;
                st.push_back(nums[i]);
                if (Solve()) return true;
                st.pop_back();
                used[i] = false; --used_cnt;
            }
            return false;
        }
        bool judgePoint24(vector<int>& inums) {
            nums = inums;
            used.clear();
            used.resize(nums.size());
            st.clear();
            used_cnt = 0;
            return Solve();
        }
    };
    

Log in to reply
 

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