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