题目描述：

LeetCode 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.

题目大意：

给定4个范围1~9的数字，判断是否可以利用四则运算和括号，组成24。

解题思路：

递归（Recursion）

Python代码：

class Solution(object):
    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return any(abs(x - 24) < 1e-9 for x in self.solve(nums))
    def solve(self, nums):
        size = len(nums)
        if size == 1: return [nums[0]]
        ans = []
        for x in range(size):
            left, n = nums[x], nums[ : x] + nums[x + 1 : ]
            for right in self.solve(n):
                ans.append(left + right)
                ans.append(left - right)
                ans.append(left * right)
                if right: ans.append(1.0 * left / right)
        if size >=3: 
            for x in range(size):
                for y in range(x + 1, size):
                    left, right = nums[x], nums[y]
                    n = nums[:x] + nums[x + 1 : y] + nums[y + 1 : ]
                    ans += self.solve([left + right] + n)
                    ans += self.solve([left - right] + n)
                    ans += self.solve([left * right] + n)
                    if right: ans += self.solve([1.0 * left / right] + n)
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/09/17/leetcode-24-game/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码