Description
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.
<ul>
<li>For example, <code>4 / (1 - 2 / 3) = 4 / (1 / 3) = 12</code>.</li>
</ul>
</li>
<li>Every operation done is between two numbers. In particular, we cannot use <code>'-'</code> as a unary operator.
<ul>
<li>For example, if <code>cards = [1, 1, 1, 1]</code>, the expression <code>"-1 - 1 - 1 - 1"</code> is <strong>not allowed</strong>.</li>
</ul>
</li>
<li>You cannot concatenate numbers together
<ul>
<li>For example, if <code>cards = [1, 2, 1, 2]</code>, the expression <code>"12 + 12"</code> is not valid.</li>
</ul>
</li>
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
Solutions
Solution 1: DFS
We design a function dfs(nums), where nums represents the current number sequence. The function returns a boolean value indicating whether there exists a permutation that makes this number sequence equal to 24.
If the length of nums is 1, we return true only when this number is 24, otherwise we return false.
Otherwise, we can enumerate any two numbers a and b in nums as the left and right operands, and enumerate the operator op between a and b. The result of a\ op\ b can be used as an element of the new number sequence. We add it to the new number sequence and remove a and b from nums, then recursively call the dfs function. If it returns true, it means we have found a permutation that makes this number sequence equal to 24, and we return true.
If none of the enumerated cases return true, we return false.
PythonJavaC++GoTypeScriptRust
class Solution:
def judgePoint24(self, cards: List[int]) -> bool:
def dfs(nums: List[float]):
n = len(nums)
if n == 1:
if abs(nums[0] - 24) < 1e-6:
return True
return False
ok = False
for i in range(n):
for j in range(n):
if i != j:
nxt = [nums[k] for k in range(n) if k != i and k != j]
for op in ops:
match op:
case "/":
if nums[j] == 0:
continue
ok |= dfs(nxt + [nums[i] / nums[j]])
case "*":
ok |= dfs(nxt + [nums[i] * nums[j]])
case "+":
ok |= dfs(nxt + [nums[i] + nums[j]])
case "-":
ok |= dfs(nxt + [nums[i] - nums[j]])
if ok:
return True
return ok
ops = ("+", "-", "*", "/")
nums = [float(x) for x in cards]
return dfs(nums)(code-box)
class Solution {
private final char[] ops = {'+', '-', '*', '/'};
public boolean judgePoint24(int[] cards) {
List<Double> nums = new ArrayList<>();
for (int num : cards) {
nums.add((double) num);
}
return dfs(nums);
}
private boolean dfs(List<Double> nums) {
int n = nums.size();
if (n == 1) {
return Math.abs(nums.get(0) - 24) < 1e-6;
}
boolean ok = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) {
List<Double> nxt = new ArrayList<>();
for (int k = 0; k < n; ++k) {
if (k != i && k != j) {
nxt.add(nums.get(k));
}
}
for (char op : ops) {
switch (op) {
case '/' -> {
if (nums.get(j) == 0) {
continue;
}
nxt.add(nums.get(i) / nums.get(j));
}
case '*' -> {
nxt.add(nums.get(i) * nums.get(j));
}
case '+' -> {
nxt.add(nums.get(i) + nums.get(j));
}
case '-' -> {
nxt.add(nums.get(i) - nums.get(j));
}
}
ok |= dfs(nxt);
if (ok) {
return true;
}
nxt.remove(nxt.size() - 1);
}
}
}
}
return ok;
}
}(code-box)
class Solution {
public:
bool judgePoint24(vector<int>& cards) {
vector<double> nums;
for (int num : cards) {
nums.push_back(static_cast<double>(num));
}
return dfs(nums);
}
private:
const char ops[4] = {'+', '-', '*', '/'};
bool dfs(vector<double>& nums) {
int n = nums.size();
if (n == 1) {
return abs(nums[0] - 24) < 1e-6;
}
bool ok = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) {
vector<double> nxt;
for (int k = 0; k < n; ++k) {
if (k != i && k != j) {
nxt.push_back(nums[k]);
}
}
for (char op : ops) {
switch (op) {
case '/':
if (nums[j] == 0) {
continue;
}
nxt.push_back(nums[i] / nums[j]);
break;
case '*':
nxt.push_back(nums[i] * nums[j]);
break;
case '+':
nxt.push_back(nums[i] + nums[j]);
break;
case '-':
nxt.push_back(nums[i] - nums[j]);
break;
}
ok |= dfs(nxt);
if (ok) {
return true;
}
nxt.pop_back();
}
}
}
}
return ok;
}
};(code-box)
func judgePoint24(cards []int) bool {
ops := [4]rune{'+', '-', '*', '/'}
nums := make([]float64, len(cards))
for i, num := range cards {
nums[i] = float64(num)
}
var dfs func([]float64) bool
dfs = func(nums []float64) bool {
n := len(nums)
if n == 1 {
return math.Abs(nums[0]-24) < 1e-6
}
ok := false
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if i != j {
var nxt []float64
for k := 0; k < n; k++ {
if k != i && k != j {
nxt = append(nxt, nums[k])
}
}
for _, op := range ops {
switch op {
case '/':
if nums[j] == 0 {
continue
}
nxt = append(nxt, nums[i]/nums[j])
case '*':
nxt = append(nxt, nums[i]*nums[j])
case '+':
nxt = append(nxt, nums[i]+nums[j])
case '-':
nxt = append(nxt, nums[i]-nums[j])
}
ok = ok || dfs(nxt)
if ok {
return true
}
nxt = nxt[:len(nxt)-1]
}
}
}
}
return ok
}
return dfs(nums)
}(code-box)
function judgePoint24(cards: number[]): boolean {
const ops: string[] = ['+', '-', '*', '/'];
const dfs = (nums: number[]): boolean => {
const n: number = nums.length;
if (n === 1) {
return Math.abs(nums[0] - 24) < 1e-6;
}
let ok: boolean = false;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (i !== j) {
const nxt: number[] = [];
for (let k = 0; k < n; k++) {
if (k !== i && k !== j) {
nxt.push(nums[k]);
}
}
for (const op of ops) {
switch (op) {
case '/':
if (nums[j] === 0) {
continue;
}
nxt.push(nums[i] / nums[j]);
break;
case '*':
nxt.push(nums[i] * nums[j]);
break;
case '+':
nxt.push(nums[i] + nums[j]);
break;
case '-':
nxt.push(nums[i] - nums[j]);
break;
}
ok = ok || dfs(nxt);
if (ok) {
return true;
}
nxt.pop();
}
}
}
}
return ok;
};
return dfs(cards);
}(code-box)
impl Solution {
pub fn judge_point24(cards: Vec<i32>) -> bool {
fn dfs(nums: Vec<f64>) -> bool {
let n = nums.len();
if n == 1 {
return (nums[0] - 24.0).abs() < 1e-6;
}
for i in 0..n {
for j in 0..n {
if i == j {
continue;
}
let mut nxt = Vec::new();
for k in 0..n {
if k != i && k != j {
nxt.push(nums[k]);
}
}
for op in 0..4 {
let mut nxt2 = nxt.clone();
match op {
0 => {
nxt2.push(nums[i] + nums[j]);
}
1 => {
nxt2.push(nums[i] - nums[j]);
}
2 => {
nxt2.push(nums[i] * nums[j]);
}
3 => {
if nums[j].abs() < 1e-6 {
continue;
}
nxt2.push(nums[i] / nums[j]);
}
_ => {}
}
if dfs(nxt2) {
return true;
}
}
}
}
false
}
let nums: Vec<f64> = cards.into_iter().map(|x| x as f64).collect();
dfs(nums)
}
}(code-box)
