Leetcode:No.679 24 Game

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点游戏，不过这里每个数都是1-9，并不是扑克牌。题目并没有直说4个都要用到，但是看例子是这个意思，实际上也是这个意思。
这个题目有一个不大不小的坑，需要对计算机系统有一定了解，一般算法题还涉及不到，那就是浮点数的精度丢失。有兴趣的可以去搜索或者参考这篇文章，这里不多讲，只是在做题的时候留个心眼，不能直接比较24，而是引进一个足够小的数eps来抵消误差。这里因为数字小，步骤也不多，所以eps=0.001足够了。
也就是说，只要数值x满足abs(x-24) <= eps我们就认为x=24.

那么具体到问题中来。24点我们自然不陌生，但是要怎么下手呢？举例好像没什么用，毕竟有时候我们自己也不知道怎么解。看起来只能采用“暴力”一点的方法了。好在数字小，4个数的，4种基础运算方式，怎么折腾都翻不了天。
括号的加入让问题看起来复杂了一些，但是本质上不影响。因为还是可以逐对计算，而如果全部可能都覆盖到的话，括号自然也就考虑到了。
所以初步判断这是一个DFS或者递归的问题。关于这类问题平时有一个需要考虑的就是剪枝，不过这里还是因为数字小，另外其实也不好剪，除非你算一下不然你怎么知道可不可以呢？

好吧，那就尝试开始编。排序是没必要了，结果可能会搞乱顺序。
递归解法：

# 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一点。
虽说暴力，但是能优化还是尽量优化，比如加法乘法就没必要换个顺序再来一遍，另外除数为0也不行。
这些对应if ((op is add or op is mul) and j > i) or (op == truediv and abs(nums[j]) <= 1e-3):这个条件。
另外这个先append试一试再pop出来，英文里面叫做back tracking，即回溯，是面对同类问题里面经常使用的方法，好处就是和下一层分离，等递归回来以后可以当无事发生过继续下一个，值得了解一下。

总结：

算是比较典型的DFS递归问题。