Welcome to Subscribe On Youtube
679. 24 Game
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.- 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
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$.
-
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; } } -
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; } }; -
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) -
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) } -
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); }