LeetCode 679題 24 Game 解題筆記

題目描述
給定四個整數卡牌，請判斷是否能透過加
+
、減

、乘
*
、除
/
以及括號的任意組合，讓最終結果等於
24
。
允許使用浮點數計算，但最終答案誤差需在 $10^{-6}$ 以內。
範例
範例 1：
輸入：
cards = [4, 1, 8, 7]
輸出：
true
解釋：
$(8 - 4) \times (7 - 1) = 24$
範例 2：
輸入：
cards = [1, 2, 1, 2]
輸出：
false
Constraints
卡牌數固定為 4 張
每張卡牌的數字範圍：1 <= card[i] <= 9
解題思路
這題是典型的
回溯 (DFS + Backtracking)
題目。
我們需要嘗試所有數字間的
排列組合
，並搭配四則運算。
遞迴設計：
當只剩一個數字時，檢查是否接近 24 (
fabs(x-24) < 1e-6
)。
誤差範圍 1e-6 都可以
否則，從陣列中選兩個數字，對它們進行
六種可能運算
：
a + b
a - b
b - a
a * b
a / b
(若 b != 0)
b / a
(若 a != 0)
Tips : b != 0 以及 a != 0 要寫做 fabs(a) > 1e-6 避免微小誤差影響結果。
fabs是絕對值
遞迴繼續處理剩下的數字。
一旦找到符合 24 的情況就回傳
true
。
這其實是一種
全排列 + 搜尋
的做法，暴力但可行，因為數字數量只有 4 個。
範例解題 - {4, 1, 8, 7} 為例子
Start: {4, 1, 8, 7}

開始: [4, 1, 8, 7]
├─ 選 (4,1)
│   ├─ 4+1=5 → [5,8,7]
│   │   ├─ 選 (5,8)
│   │   │   ├─ 5+8=13 → [13,7] → ...
│   │   │   ├─ 5-8=-3 → [7,-3] → ...
│   │   │   ├─ 8-5=3 → [7,3] → ...
│   │   │   ├─ 5*8=40 → [40,7] → ...
│   │   │   ├─ 5/8=0.625 → [0.625,7] → ...
│   │   │   └─ 8/5=1.6 → [1.6,7] → ...
│   │   └─ 選 (5,7)
│   │       ├─ 5+7=12 → [12,8] → ...
│   │       ├─ 5-7=-2 → [8,-2] → ...
│   │       ├─ 7-5=2 → [8,2] → ...
│   │       ├─ 5*7=35 → [35,8] → ...
│   │       ├─ 5/7≈0.714 → [0.714,8] → ...
│   │       └─ 7/5=1.4 → [1.4,8] → ...
│   ├─ 4-1=3 → [3,8,7] → ...
│   ├─ 1-4=-3 → [-3,8,7] → ...
│   ├─ 4*1=4 → [4,8,7] → ...
│   ├─ 4/1=4 → [4,8,7] → ...
│   └─ 1/4=0.25 → [0.25,8,7] → ...
│
├─ 選 (4,8)
│   ├─ 4+8=12 → [12,1,7]
│   ├─ 4-8=-4 → [-4,1,7]
│   ├─ 8-4=4 → [4,1,7]
│   ├─ 4*8=32 → [32,1,7]
│   ├─ 4/8=0.5 → [0.5,1,7]
│   └─ 8/4=2 → [2,1,7]
│
├─ 選 (4,7)
│   ├─ 4+7=11 → [11,1,8]
│   ├─ 4-7=-3 → [-3,1,8]
│   ├─ 7-4=3 → [3,1,8]
│   ├─ 4*7=28 → [28,1,8]
│   ├─ 4/7≈0.571 → [0.571,1,8]
│   └─ 7/4=1.75 → [1.75,1,8]
│
├─ 選 (1,8)
│   ├─ 1+8=9 → [9,4,7]
│   ├─ 1-8=-7 → [-7,4,7]
│   ├─ 8-1=7 → [7,4,7]
│   ├─ 1*8=8 → [8,4,7]
│   ├─ 1/8=0.125 → [0.125,4,7]
│   └─ 8/1=8 → [8,4,7]
│
├─ 選 (1,7)
│   ├─ 1+7=8 → [8,4,8]
│   ├─ 1-7=-6 → [-6,4,8]
│   ├─ 7-1=6 → [6,4,8]
│   ├─ 1*7=7 → [7,4,8]
│   ├─ 1/7≈0.143 → [0.143,4,8]
│   └─ 7/1=7 → [7,4,8]
│
└─ 選 (8,7)
    ├─ 8+7=15 → [15,4,1]
    ├─ 8-7=1 → [1,4,1]
    ├─ 7-8=-1 → [-1,4,1]
    ├─ 8*7=56 → [56,4,1]
    ├─ 8/7≈1.143 → [1.143,4,1]
    └─ 7/8=0.875 → [0.875,4,1]

範例樹狀圖
以下為範例樹狀圖
參考程式碼（C++ 範例）

#
include
 
<iostream>
#
include
 
<vector>
#
include
 
<algorithm>
#
include
 
<math.h>
using
 
namespace
 std;
class
 
Solution
{
public
:
    
// 主函式，將整數卡牌轉成浮點數後開始 DFS 遞迴
    
bool
 
judgePoint24
(vector<
int
> &cards)
    
{
        vector<
double
> nums;
        
for
 (
int
 c : cards)
            nums.
push_back
((
double
)c);  
// 將整數轉成 double 方便後續運算
        
return
 
dfs
(nums);
    }
    
// 遞迴函式：判斷當前數字集合是否能組成 24
    
bool
 
dfs
(vector<
double
> &nums)
    
{
        
if
 (nums.
size
() == 
1
)
            
// 如果只剩一個數字，檢查是否接近 24
            
return
 
fabs
(nums[
0
] - 
24
) < 
1e-6
;
        
int
 n = nums.
size
();
        
// 選擇兩個不同的數字進行運算
        
for
 (
int
 i = 
0
; i < n - 
1
; i++)
        {
            
for
 (
int
 j = i + 
1
; j < n; j++)
            {
                vector<
double
> next;
                
// 將未被選中的數字放入 next，作為下一輪遞迴的集合
                
for
 (
int
 k = 
0
; k < n; k++)
                    
if
 (k != i && k != j) next.
push_back
(nums[k]);
                
// 計算兩個數字所有可能的運算結果
                
for
 (
double
 res : 
compute
(nums[i], nums[j]))
                {
                    next.
push_back
(res);      
// 將結果加入集合
                    
if
 (
dfs
(next)) 
return
 
true
; 
// 遞迴，如果找到 24，直接返回 true
                    next.
pop_back
();          
// 回溯，移除剛加入的數字
                }
            }
        }
        
return
 
false
; 
// 所有組合都不能得到 24
    }
    
// 計算兩個數字所有可能的運算結果
    
vector<
double
> 
compute
(
double
 a, 
double
 b)
    
{
        vector<
double
> results;
        results.
push_back
(a + b);  
// 加法
        results.
push_back
(a - b);  
// a - b
        results.
push_back
(b - a);  
// b - a
        results.
push_back
(a * b);  
// 乘法
        
if
 (
fabs
(a) > 
1e-6
) results.
push_back
(b / a); 
// b / a，避免除以 0
        
if
 (
fabs
(b) > 
1e-6
) results.
push_back
(a / b); 
// a / b，避免除以 0
        
return
 results;
    }
};

複雜度分析
時間複雜度：$O( (n!) \times ops )$，其中 $n=4$，運算符號數量有限，因此實際情況仍可接受。
空間複雜度：$O(n)$，遞迴深度與數字數量相關。
LeetCode 成績
Runtime：19 ms — Beats 56.17% of C++ users
Memory：16.04 MB — Beats 55.73% of C++ users
補充說明
這題雖然是 Hard，但其實是窮舉 (brute force) 題目，
只要能正確處理浮點數精度問題，就能順利 AC

題目描述 給定四個整數卡牌，請判斷是否能透過加 + 、減

題目描述
給定四個整數卡牌，請判斷是否能透過加
+
、減