class Solution:
def judgePoint24(self, nums):
def dfs(nums):
if len(nums) == 1:
return abs(nums[0] - 24) < 1e-6
for i in range(len(nums)):
for j in range(len(nums)):
if i == j:
continue
n1, n2 = nums[i], nums[j]
next_nums = [nums[k] for k in range(len(nums)) if k != i and k != j]
for op in ['+', '-', '*', '/']:
if op == '+':
res = n1 + n2
elif op == '-':
res = n1 - n2
elif op == '*':
res = n1 * n2
elif op == '/':
if abs(n2) < 1e-6:
continue
res = n1 / n2
if dfs(next_nums + [res]):
return True
return False
return dfs([float(x) for x in nums])
class Solution {
public:
bool judgePoint24(vector<int>& nums) {
vector<double> arr(nums.begin(), nums.end());
return dfs(arr);
}
bool dfs(vector<double>& nums) {
if (nums.size() == 1)
return fabs(nums[0] - 24) < 1e-6;
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < nums.size(); ++j) {
if (i == j) continue;
vector<double> next;
for (int k = 0; k < nums.size(); ++k)
if (k != i && k != j) next.push_back(nums[k]);
for (int op = 0; op < 4; ++op) {
if (op < 2 && i > j) continue; // avoid duplicate
double res = 0.0;
if (op == 0) res = nums[i] + nums[j];
if (op == 1) res = nums[i] * nums[j];
if (op == 2) res = nums[i] - nums[j];
if (op == 3) {
if (fabs(nums[j]) < 1e-6) continue;
res = nums[i] / nums[j];
}
next.push_back(res);
if (dfs(next)) return true;
next.pop_back();
}
}
}
return false;
}
};
class Solution {
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<>();
for (int n : nums) list.add((double) n);
return dfs(list);
}
private boolean dfs(List<Double> nums) {
if (nums.size() == 1)
return Math.abs(nums.get(0) - 24) < 1e-6;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size(); j++) {
if (i == j) continue;
List<Double> next = new ArrayList<>();
for (int k = 0; k < nums.size(); k++)
if (k != i && k != j) next.add(nums.get(k));
for (int op = 0; op < 4; op++) {
if (op < 2 && i > j) continue;
double res = 0;
if (op == 0) res = nums.get(i) + nums.get(j);
if (op == 1) res = nums.get(i) * nums.get(j);
if (op == 2) res = nums.get(i) - nums.get(j);
if (op == 3) {
if (Math.abs(nums.get(j)) < 1e-6) continue;
res = nums.get(i) / nums.get(j);
}
next.add(res);
if (dfs(next)) return true;
next.remove(next.size() - 1);
}
}
}
return false;
}
}
var judgePoint24 = function(nums) {
function dfs(arr) {
if (arr.length === 1) {
return Math.abs(arr[0] - 24) < 1e-6;
}
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i === j) continue;
let next = [];
for (let k = 0; k < arr.length; k++) {
if (k !== i && k !== j) next.push(arr[k]);
}
for (let op of ['+', '-', '*', '/']) {
if (op === '+') {
next.push(arr[i] + arr[j]);
} else if (op === '-') {
next.push(arr[i] - arr[j]);
} else if (op === '*') {
next.push(arr[i] * arr[j]);
} else if (op === '/') {
if (Math.abs(arr[j]) < 1e-6) continue;
next.push(arr[i] / arr[j]);
}
if (dfs(next)) return true;
next.pop();
}
}
}
return false;
}
return dfs(nums.map(x => x * 1.0));
};
Given an array nums of exactly four integers, you must determine if you can use each number exactly once, along with any combination of the four basic arithmetic operations (+, -, *, /) and parentheses, to reach the number 24.
true if it is possible to reach 24, otherwise false.At first glance, this problem seems like a brute-force search: try every possible combination of numbers, operations, and order of operations. However, there are many possible ways to combine four numbers and operations, especially since parentheses can dramatically change the result.
The main challenge is to systematically consider all possible ways to combine the numbers with operations, while ensuring each number is used only once and all possible groupings (i.e., with parentheses) are considered.
We quickly realize that brute-forcing all permutations and operations is feasible because there are only four numbers. But to avoid redundant calculations and make the code manageable, we need a recursive approach that, at each step, combines two numbers with an operation and recurses on the resulting list.
Floating-point precision is another concern: some results may be very close to 24 but not exactly 24 due to division, so we must check if the result is "close enough".
- and /), try both orders.
1e-6).
true, propagate that result up.
This approach ensures all possible groupings and operation orders are explored, but avoids redundant work by not reusing numbers or repeating the same pair in both orders for commutative operations.
Let's use nums = [4, 1, 8, 7] as an example.
true.
false.
The recursive exploration ensures all combinations and groupings are checked.
Brute-Force Approach:
The 24 Game problem is a classic example of recursive backtracking. By systematically combining pairs of numbers with all possible operations and recursing, we can check if any sequence of operations produces 24. Key insights include handling floating-point precision, pruning impossible branches early, and realizing that the problem size is small enough to allow a brute-force recursive solution. This approach is elegant in its simplicity and exhaustiveness, ensuring all valid expressions are considered.