## Algorithm

Problem Name: 679. 24 Game

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:

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

Example 2:

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

Constraints:

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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool judgePoint24(vector& nums) {
unordered_setres;
string ops = "+-*/";
dfs(nums, "", ops, res);
for (auto& x: res) {
auto v = getResult(x);
if (!v.empty() && abs(v.back() - 24) < 0.0001) {
return true;
}
}
return false;
}

// Generate all possible permutations
void dfs(vector& nums, string s, string& ops, unordered_set& res) {
for (int& x: nums) {
if (x == 0) {
continue;
}
int tmp = x;
s.push_back(x + '0');
x = 0;

if (s.size() == 7) {
res.insert(s);
s.pop_back();
x = tmp;
return;
}

for (auto c: ops) {
s.push_back(c);
dfs(nums, s, ops, res);
s.pop_back();
}
s.pop_back();
x = tmp;
}
}

// Generate all possible results from string 's'
vector getResult(string s) {
int n = s.size();
if (n == 1) {
return {s[0] - '0'};
}
vectorres;
for (int i = 1; i <= n - 2; i += 2) {
vector l = getResult(s.substr(0, i));
vector r = getResult(s.substr(i + 1));
char op = s[i];

for (auto& x: l) {
for (auto& y: r) {
if (op == '/' && !y) {
continue;
}
double val = helper(op, x, y);
res.push_back(val);
if (s.size() == 7 && abs(val - 24) < 0.0001) {
return res;
}
}
}
}
return res;
}

double helper(char op, double a, double b) {
if (op == '+') {
a += b;
} else if (op == '-') {
a -= b;
} else if (op == '*') {
a *= b;
} else {
a /= b;
}
return a;
}
};
``````
Copy The Code &

Input

cmd
cards = [4,1,8,7]

Output

cmd
true

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const judgePoint24 = function(nums) {
return dfs(nums)
}

function dfs(list) {
let eps = 0.0001
if (list.length === 1) {
if (Math.abs(list[0] - 24) < eps) {
return true
}
return false
}
let n = list.length
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const next = new Array(n - 1)
for (let k = 0, index = 0; k < n; k++) {
if (k !== i && k !== j) next[index++] = list[k]
}
let d1 = list[i],
d2 = list[j]
const dirs = [d1 + d2, d1 - d2, d2 - d1, d2 * d1]
if (d1 > eps) dirs.push(d2 / d1)
if (d2 > eps) dirs.push(d1 / d2)
for (let dir of dirs) {
next[n - 2] = dir
if (dfs(next)) return true
}
}
}
return false
}
``````
Copy The Code &

Input

cmd
cards = [4,1,8,7]

Output

cmd
true

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def judgePoint24(self, nums):
q = [[None, nums[i]] + nums[:i] + nums[i + 1:] for i in range(len(nums))]
while q:
new = []
for group1, group2, *rest in q:
if not rest and group1:
for res in (group1 + group2, group1 - group2, group1 * group2, group2 and group1 / group2):
if 23.999 <= res <= 24.0001: return True
if not rest and not group1 and 23.999 <= group2 <= 24.0001: return True
for i in range(len(rest)):
for newGroup2 in (group2 + rest[i], group2 - rest[i], rest[i] - group2, group2 * rest[i], group2 / rest[i]):
new.append([group1, newGroup2] + rest[:i] + rest[i + 1:])
if group2:
new.append([group1, rest[i] / group2] + rest[:i] + rest[i + 1:])
if group1 != None:
for newGroup1 in (group1 + group2, group1 - group2, group1 * group2):
new.append([newGroup1, rest[i]] + rest[:i] + rest[i + 1:])
if group2:
new.append([group1 / group2, rest[i]] + rest[:i] + rest[i + 1:])
else:
new.append([group2, rest[i]] + rest[:i] + rest[i + 1:])
q = new
return False
``````
Copy The Code &

Input

cmd
cards = [1,2,1,2]

Output

cmd
false