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:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. 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.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

24點(diǎn)游戲，不過這里每個(gè)數(shù)都是1-9，并不是撲克牌。題目并沒有直說4個(gè)都要用到，但是看例子是這個(gè)意思，實(shí)際上也是這個(gè)意思。
這個(gè)題目有一個(gè)不大不小的坑，需要對(duì)計(jì)算機(jī)系統(tǒng)有一定了解，一般算法題還涉及不到，那就是浮點(diǎn)數(shù)的精度丟失。有興趣的可以去搜索或者參考這篇文章，這里不多講，只是在做題的時(shí)候留個(gè)心眼，不能直接比較24，而是引進(jìn)一個(gè)足夠小的數(shù)eps來抵消誤差。這里因?yàn)閿?shù)字小，步驟也不多，所以eps=0.001足夠了。
也就是說，只要數(shù)值x滿足abs(x-24) <= eps我們就認(rèn)為x=24.

那么具體到問題中來。24點(diǎn)我們自然不陌生，但是要怎么下手呢？舉例好像沒什么用，畢竟有時(shí)候我們自己也不知道怎么解?？雌饋碇荒懿捎谩氨┝Α币稽c(diǎn)的方法了。好在數(shù)字小，4個(gè)數(shù)的，4種基礎(chǔ)運(yùn)算方式，怎么折騰都翻不了天。
括號(hào)的加入讓問題看起來復(fù)雜了一些，但是本質(zhì)上不影響。因?yàn)檫€是可以逐對(duì)計(jì)算，而如果全部可能都覆蓋到的話，括號(hào)自然也就考慮到了。
所以初步判斷這是一個(gè)DFS或者遞歸的問題。關(guān)于這類問題平時(shí)有一個(gè)需要考慮的就是剪枝，不過這里還是因?yàn)閿?shù)字小，另外其實(shí)也不好剪，除非你算一下不然你怎么知道可不可以呢？

好吧，那就嘗試開始編。排序是沒必要了，結(jié)果可能會(huì)搞亂順序。
遞歸解法：

# 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

其實(shí)用operator沒啥必要，就是看起來cool一點(diǎn)。
雖說暴力，但是能優(yōu)化還是盡量?jī)?yōu)化，比如加法乘法就沒必要換個(gè)順序再來一遍，另外除數(shù)為0也不行。
這些對(duì)應(yīng)if ((op is add or op is mul) and j > i) or (op == truediv and abs(nums[j]) <= 1e-3):這個(gè)條件。
另外這個(gè)先append試一試再pop出來，英文里面叫做back tracking，即回溯，是面對(duì)同類問題里面經(jīng)常使用的方法，好處就是和下一層分離，等遞歸回來以后可以當(dāng)無事發(fā)生過繼續(xù)下一個(gè)，值得了解一下。

總結(jié)：

算是比較典型的DFS遞歸問題。