24 Game Problem


Description

LeetCode Problem 679.

You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators [’+’, ‘-‘, ‘*’, ‘/’] and the parentheses ‘(‘ and ‘)’ to get the value 24. You are restricted with the following rules:

  • The division operator ‘/’ represents real division, not integer division.
  • For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
  • Every operation done is between two numbers. In particular, we cannot use ‘-‘ as a unary operator.
  • For example, if cards = [1, 1, 1, 1], the expression “-1 - 1 - 1 - 1” is not allowed.
  • You cannot concatenate numbers together
  • For example, if cards = [1, 2, 1, 2], the expression “12 + 12” is not valid.

Return true if you can get such expression that evaluates to 24, and false otherwise.

Example 1:

1
2
3
Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

Example 2:

1
2
Input: cards = [1,2,1,2]
Output: false

Constraints:

  • cards.length == 4
  • 1 <= cards[i] <= 9


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        do {
            if (valid(nums)) return true;
        } while(next_permutation(nums.begin(), nums.end()));
        return false;
    }
    
private:
    bool valid(vector<int>& nums) {
        double a = nums[0], b = nums[1], c = nums[2], d = nums[3];
        if (valid(a+b, c, d) || valid(a-b, c, d) || valid(a*b, c, d) || valid(a/b, c, d)) return true;
        if (valid(a, b+c, d) || valid(a, b-c, d) || valid(a, b*c, d) || valid(a, b/c, d)) return true;
        if (valid(a, b, c+d) || valid(a, b, c-d) || valid(a, b, c*d) || valid(a, b, c/d)) return true;
        return false;
    }
    
    bool valid(double a, double b, double c) {
        if (valid(a+b, c) || valid(a-b, c) || valid(a*b, c) || b&&valid(a/b, c)) return true;
        if (valid(a, b+c) || valid(a, b-c) || valid(a, b*c) || c&&valid(a, b/c)) return true;
        return false;
    }
    
    bool valid(double a, double b) {
        if (abs(a+b-24.0) < 0.0001 || abs(a-b-24.0) < 0.0001 || abs(a*b-24.0) < 0.0001 || b&&abs(a/b-24.0) < 0.0001) 
            return true;
        return false;
    }
};




Related Posts

Unique Paths III Problem

LeetCode 980. You are given an m x n integer...

Split Array Into Fibonacci Sequence Problem

LeetCode 842. You are given a string of digits num,...

Partition To K Equal Sum Subsets Problem

LeetCode 698. Given an integer array nums and an integer...

Letter Case Permutation Problem

LeetCode 784. Given a string s, we can transform every...

24 Game Problem

LeetCode 679. You are given an integer array cards of...

Matchsticks To Square Problem

LeetCode 473. You are given an integer array matchsticks where...