You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.
Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24
Example 2:
Input: [1, 2, 1, 2]
Output: False
Note:
- The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
- Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
- You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.
24點游戲，不過這里每個數(shù)都是1-9国葬，并不是撲克牌慧耍。題目并沒有直說4個都要用到诬像，但是看例子是這個意思跪腹，實際上也是這個意思。
這個題目有一個不大不小的坑开伏，需要對計算機系統(tǒng)有一定了解膀跌，一般算法題還涉及不到，那就是浮點數(shù)的精度丟失固灵。有興趣的可以去搜索或者參考這篇文章捅伤，這里不多講，只是在做題的時候留個心眼巫玻，不能直接比較24丛忆，而是引進一個足夠小的數(shù)eps來抵消誤差。這里因為數(shù)字小仍秤，步驟也不多熄诡，所以eps=0.001足夠了。
也就是說诗力，只要數(shù)值x滿足abs(x-24) <= eps我們就認為x=24.
那么具體到問題中來凰浮。24點我們自然不陌生，但是要怎么下手呢姜骡？舉例好像沒什么用导坟，畢竟有時候我們自己也不知道怎么解∪Τ海看起來只能采用“暴力”一點的方法了惫周。好在數(shù)字小，4個數(shù)的康栈，4種基礎(chǔ)運算方式递递，怎么折騰都翻不了天。
括號的加入讓問題看起來復(fù)雜了一些啥么，但是本質(zhì)上不影響登舞。因為還是可以逐對計算，而如果全部可能都覆蓋到的話悬荣，括號自然也就考慮到了菠秒。
所以初步判斷這是一個DFS或者遞歸的問題。關(guān)于這類問題平時有一個需要考慮的就是剪枝氯迂，不過這里還是因為數(shù)字小践叠，另外其實也不好剪，除非你算一下不然你怎么知道可不可以呢嚼蚀？
好吧禁灼，那就嘗試開始編。排序是沒必要了轿曙，結(jié)果可能會搞亂順序弄捕。
遞歸解法：
# Time: O(n^3 * 4^n) = O(1), n = 4
# Space: O(n^2) = O(1)
from operator import add, sub, mul, truediv
class Solution(object):
def judgePoint24(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums) == 1:
return abs(nums[0]-24) <= 1e-3
ops = [add, sub, mul, truediv]
for i in xrange(len(nums)):
for j in xrange(len(nums)):
if i == j:
continue
next_nums = [nums[k] for k in xrange(len(nums)) if i != k != j]
for op in ops:
if ((op is add or op is mul) and j > i) or \
(op == truediv and abs(nums[j]) <= 1e-3):
continue
next_nums.append(op(nums[i], nums[j]))
if self.judgePoint24(next_nums):
return True
next_nums.pop()
return False
其實用operator沒啥必要僻孝，就是看起來cool一點。
雖說暴力守谓，但是能優(yōu)化還是盡量優(yōu)化穿铆，比如加法乘法就沒必要換個順序再來一遍，另外除數(shù)為0也不行分飞。
這些對應(yīng)if ((op is add or op is mul) and j > i) or (op == truediv and abs(nums[j]) <= 1e-3):這個條件悴务。
另外這個先append試一試再pop出來，英文里面叫做back tracking譬猫，即回溯讯檐，是面對同類問題里面經(jīng)常使用的方法，好處就是和下一層分離染服，等遞歸回來以后可以當(dāng)無事發(fā)生過繼續(xù)下一個别洪，值得了解一下。
總結(jié)：
算是比較典型的DFS遞歸問題柳刮。
