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;
}
};