链接：LeetCode679
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
示例 1:
输入: ([4, 1, 8, 7])
输出: True
解释: (8-4) * (7-1) = 24
示例 2:
输入: ([1, 2, 1, 2])
输出: False
注意:
除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 ([1, 2, 1, 2]) 时，不能写成 12 + 12 。
相关标签：深度优先搜索
也是一道很明显的深度优先搜索题。其难点在于，每一次搜索我们要在数组中取两个数进行运行运算之后，加入新的数组进行深度遍历。
注意，与之前不同的，我们不能设置单个变量进行搜索，因为有括号的因素存在，可能会出现两个数分别做加减，再做乘除的可能。
代码如下：
python:
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
return self.helper(nums)
def helper(self,nums):
if len(nums) == 1:
return abs(nums[0]-24) < 0.01
else:
for i in range(len(nums)):
for j in range(len(nums)):
if j==i:continue
new = []
for k in range(len(nums)):
if k!=i and k!=j:
new.append(nums[k])
for k in range(4):
if k==0:
new.append(nums[i]+nums[j])
if k==1:
new.append(nums[i]-nums[j])
if k==2:
new.append(nums[i]*nums[j])
if k==3:
if nums[j]!=0:
new.append(nums[i]/nums[j])
else:continue
if self.helper(new):
return True
new = new[:-1]
return False
C++:
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 abs(nums[0]-24)<0.01;
}
for (int i=0;i!=nums.size();++i){
for (int j=0;j!=nums.size();++j) {
if(i==j) continue;
vector<double> v;
for(int k=0;k!=nums.size();++k){
if(k!=i&&k!=j) v.push_back(nums[k]);
}
string ops = "+-*/";
double p=nums[i],q=nums[j];
for(char ch:ops){
if(ch=='/' && abs(q)<0.01) continue;
switch(ch) {
case '+':v.push_back(p+q);break;
case '-':v.push_back(p-q);break;
case '*':v.push_back(p*q);break;
case '/':v.push_back(p/q);break;
}
if(dfs(v)) return true;
v.pop_back();
}
}
}
return false;
}
};