24 Game


  • 1

    Click here to see the full article post


  • 0
    C

    can you provide c++ solution, thanks


  • 1

    @codingcrazer

    class Solution {
    public:
        bool judgePoint24(vector<int>& nums) {
            vector<double> A;
            for (int v: nums) A.push_back(v);
            return solve(A);
        }
        bool solve(vector<double>& A) {
            if (A.empty()) return false;
            if (A.size() == 1) return abs(A[0] - 24) < 1e-6;
            
            for (int i = 0; i < A.size(); i++) {
                for (int j = 0; j < A.size(); j++) if (i != j) {
                    vector<double> B;
                    for (int k = 0; k < A.size(); k++) {
                        if (k != i && k != j) B.push_back(A[k]);
                    }
                    for (int k = 0; k < 4; k++) {
                        if (k == 0) B.push_back(A[i] + A[j]);
                        if (k == 1) B.push_back(A[i] - A[j]);
                        if (k == 2) B.push_back(A[i] * A[j]);
                        if (k == 3 && A[j] != 0) B.push_back(A[i] / A[j]);
                        if (solve(B)) return true;
                        B.pop_back();
                    }
                }
            }
            return false;
        }
    };
    

  • 0
    G
    import Data.List (permutations)
    import Control.Monad (guard)
    
    ops = [(+), (-), (*), (/)]
    
    solve ns = not . null $ do
        [x, y, z, w] <- permutations ns
        f <- ops
        g <- ops
        h <- ops
        guard $ f (g (h x y) z) w == 24
             || f (g x y) (h z w) == 24
             || f x (g y (h z w)) == 24
    

  • 0
    O

    Can someone explain to me why there are 12∗6∗2∗4∗4∗4 possibilities?


  • 0

    @okdolly Say we have numbers a, b, c, d. We choose two of them (with order) in 12 ways and perform one of 4 operations. This is where 12 * 4 comes from. Then, with 3 remaining numbers, we choose 2 of them and perform one of 4 operations. This is where 6 * 4 comes from. Finally we have two numbers left and make a final choice of 2 * 4 possibilities.


  • 0
    S

    Could you please explain how you came up with that upper bound?


  • 0

    @saiha It's 12 * 6 * 2 * 4 * 4 * 4.


  • 0
    O

    @awice Thank you so much!


  • 0
    I

    Does the space complexity count the number of recursion function in heap?


  • 0

    @isucs Yes. In terms of n, the number of initial numbers we have, the heap could get as big as O(4^n n! (n-1)!) or so. But if we have considered n to be a constant (like 4), then this would still be considered an O(1) factor.


  • 0
    C
    This post is deleted!

  • 0
    I

    @awice You descirbe n as the number of initial numbers we have, it is not the number of operations we have, why do you think you could consider that n is a constant (4 in your example) ?


  • 0
    R

    I'm looking at the Java code, and I don't see it taking into account nums.get(j) - nums.lget(i) and nums.get(j)/nums.get(i). Am I missing something?


  • 0

    @richard.zhang.969 In the initial loops, i could be greater than j already.


  • 0
    R

    @awice Thanks for pointing that out. Totally missed that.


Log in to reply
 

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