Algorithm
Problem Name: 679. 24 Game
Problem Link: https://leetcode.com/problems/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.
- For example,
- 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.
- For example, if
- You cannot concatenate numbers together
- For example, if
cards = [1, 2, 1, 2], the expression"12 + 12"is not valid.
- For example, if
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 == 41 <= cards[i] <= 9
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool judgePoint24(vector<int>& nums) {
unordered_set < string>res;
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<int>& nums, string s, string& ops, unordered_set < string>& 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 < double> getResult(string s) {
int n = s.size();
if (n == 1) {
return {s[0] - '0'};
}
vector < double>res;
for (int i = 1; i < = n - 2; i += 2) {
vector<double> l = getResult(s.substr(0, i));
vector < double> 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;
}
};
Input
cards = [4,1,8,7]
Output
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
}
Input
cards = [4,1,8,7]
Output
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
Input
cards = [1,2,1,2]
Output
false