从LeetCode 679. 24 Game--C++ 解法--二十四点 到穷举24点所有可能性-24点大全

从LeetCode 679. 24 Game–C++ 解法–二十四点 到穷举24点所有可能性

此文首发于我的个人博客：zhang0peter的个人博客

LeetCode题解文章分类：LeetCode题解文章集合
LeetCode 所有题目总结：LeetCode 所有题目总结

题目地址：24 Game - LeetCode

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

这道题目是给指定的4个数字，算二十四点。本来是一道锻炼小学生的口算能力的题，用编程来解决反而比较困难。

最容易想到的方法是穷举，最大的问题在于运算符的优先级，尤其是小括号的存在，使得直接穷举没有那么简单。

但仔细考虑后，还是穷举的解法最现实，C++解法如下：

class Solution {
public:
    bool judgePoint24(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        do {
            if (valid(nums)) return true;
        } while (next_permutation(nums.begin(), nums.end()));
        return false;
    }

private:
    inline bool valid(vector<int> &nums) {
        double a = nums[0], b = nums[1], c = nums[2], d = nums[3];
        if (valid(a + b, c, d) || valid(a - b, c, d) || valid(a * b, c, d) || valid(a / b, c, d)) return true;
        if (valid(a, b + c, d) || valid(a, b - c, d) || valid(a, b * c, d) || valid(a, b / c, d)) return true;
        if (valid(a, b, c + d) || valid(a, b, c - d) || valid(a, b, c * d) || valid(a, b, c / d)) return true;
        return false;
    }

    inline bool valid(double a, double b, double c) {
        if (valid(a + b, c) || valid(a - b, c) || valid(a * b, c) || b && valid(a / b, c)) return true;
        if (valid(a, b + c) || valid(a, b - c) || valid(a, b * c) || c && valid(a, b / c)) return true;
        return false;
    }

    inline bool valid(double a, double b) {
        if (abs(a + b - 24.0) < 0.0001 || abs(a - b - 24.0) < 0.0001 || abs(a * b - 24.0) < 0.0001 ||
            b && abs(a / b - 24.0) < 0.0001)
            return true;
        return false;
    }
};

既然单个24点可以穷举出来，那么所有的解自然可能枚举出来

事实证明现在计算机的运算速度是很快的，即使穷举也能很快算出结果。

Python穷举代码如下：

from operator import truediv, mul, add, sub

def judgePoint24(A):
    if not A:
        return False
    if len(A) == 1:
        return abs(A[0] - 24) < 1e-6
    for i in range(len(A)):
        for j in range(len(A)):
            if i != j:
                B = [A[k] for k in range(len(A)) if i != k != j]
                for op in (truediv, mul, add, sub):
                    if (op is add or op is mul) and j > i: continue
                    if op is not truediv or A[j]:
                        B.append(op(A[i], A[j]))
                        if judgePoint24(B):
                            return True
                        B.pop()
    return False

res = []
l = sorted(list(set(tuple(sorted([i, j, k, z])) for i in range(1, 11) for j in range(1, 11)
                    for k in range(1, 11) for z in range(1, 11))))
for i in l:
    if judgePoint24(i) is True:
        res.append(i)

所有的可能性大全罗列如下，共566种可能性。

1, 1, 1, 8
1, 1, 2, 6
1, 1, 2, 7
1, 1, 2, 8
1, 1, 2, 9
1, 1, 2, 10
1, 1, 3, 4
1, 1, 3, 5
1, 1, 3, 6
1, 1, 3, 7
1, 1, 3, 8
1, 1, 3, 9
1, 1, 3, 10
1, 1, 4, 4
1, 1, 4, 5
1, 1, 4, 6
1, 1, 4, 7
1, 1, 4, 8
1, 1, 4, 9
1, 1, 4, 10
1, 1, 5, 5
1, 1, 5, 6
1, 1, 5, 7
1, 1, 5, 8
1, 1, 6, 6
1, 1, 6, 8
1, 1, 6, 9
1, 1, 7, 10
1, 1, 8, 8
1, 2, 2, 4
1, 2, 2, 5
1, 2, 2, 6
1, 2, 2, 7
1, 2, 2, 8
1, 2, 2, 9
1, 2, 2, 10
1, 2, 3, 3
1, 2, 3, 4
1, 2, 3, 5
1, 2, 3, 6
1, 2, 3, 7
1, 2, 3, 8
1, 2, 3, 9
1, 2, 3, 10
1, 2, 4, 4
1, 2, 4, 5
1, 2, 4, 6
1, 2, 4, 7
1, 2, 4, 8
1, 2, 4, 9
1, 2, 4, 10
1, 2, 5, 5
1, 2, 5, 6
1, 2, 5, 7
1, 2, 5, 8
1, 2, 5, 9
1, 2, 5, 10
1, 2, 6, 6
1, 2, 6, 7
1, 2, 6, 8
1, 2, 6, 9
1, 2, 6, 10
1, 2, 7, 7
1, 2, 7, 8
1, 2, 7, 9
1, 2, 7, 10
1, 2, 8, 8
1, 2, 8, 9
1, 2, 8, 10
1, 3, 3, 3
1, 3, 3, 4
1, 3, 3, 5
1, 3, 3, 6
1, 3, 3, 7
1, 3, 3, 8
1, 3, 3, 9
1, 3, 3, 10
1, 3, 4, 4
1, 3, 4, 5
1, 3, 4, 6
1, 3, 4, 7
1, 3, 4, 8
1, 3, 4, 9
1, 3, 4, 10
1, 3, 5, 6
1, 3, 5, 7
1, 3, 5, 8
1, 3, 5, 9
1, 3, 5, 10
1, 3, 6, 6
1, 3, 6, 7
1, 3, 6, 8
1, 3, 6, 9
1, 3, 6, 10
1, 3, 7, 7
1, 3, 7, 8
1, 3, 7, 9
1, 3, 7, 10
1, 3, 8, 8
1, 3, 8, 9
1, 3, 8, 10
1, 3, 9, 9
1, 3, 9, 10
1, 3, 10, 10
1, 4, 4, 4
1, 4, 4, 5
1, 4, 4, 6
1, 4, 4, 7
1, 4, 4, 8
1, 4, 4, 9
1, 4, 4, 10
1, 4, 5, 5
1, 4, 5, 6
1, 4, 5, 7
1, 4, 5, 8
1, 4, 5, 9
1, 4, 5, 10
1, 4, 6, 6
1, 4, 6, 7
1, 4, 6, 8
1, 4, 6, 9
1, 4, 6, 10
1, 4, 7, 7
1, 4, 7, 8
1, 4, 7, 9
1, 4, 8, 8
1, 4, 8, 9
1, 4, 9, 10
1, 4, 10, 10
1, 5, 5, 5
1, 5, 5, 6
1, 5, 5, 9
1, 5, 5, 10
1, 5, 6, 6
1, 5, 6, 7
1, 5, 6, 8
1, 5, 6, 9
1, 5, 6, 10
1, 5, 7, 8
1, 5, 7, 9
1, 5, 7, 10
1, 5, 8, 8
1, 5, 8, 9
1, 5, 8, 10
1, 5, 9, 9
1, 5, 9, 10
1, 5, 10, 10
1, 6, 6, 6
1, 6, 6, 8
1, 6, 6, 9
1, 6, 6, 10
1, 6, 7, 9
1, 6, 7, 10
1, 6, 8, 8
1, 6, 8, 9
1, 6, 8, 10
1, 6, 9, 9
1, 6, 9, 10
1, 7, 7, 9
1, 7, 7, 10
1, 7, 8, 8
1, 7, 8, 9
1, 7, 8, 10
1, 7, 9, 9
1, 7, 9, 10
1, 8, 8, 8
1, 8, 8, 9
1, 8, 8, 10
2, 2, 2, 3
2, 2, 2, 4
2, 2, 2, 5
2, 2, 2, 7
2, 2, 2, 8
2, 2, 2, 9
2, 2, 2, 10
2, 2, 3, 3
2, 2, 3, 4
2, 2, 3, 5
2, 2, 3, 6
2, 2, 3, 7
2, 2, 3, 8
2, 2, 3, 9
2, 2, 3, 10
2, 2, 4, 4
2, 2, 4, 5
2, 2, 4, 6
2, 2, 4, 7
2, 2, 4, 8
2, 2, 4, 9
2, 2, 4, 10
2, 2, 5, 5
2, 2, 5, 6
2, 2, 5, 7
2, 2, 5, 8
2, 2, 5, 9
2, 2, 5, 10
2, 2, 6, 6
2, 2, 6, 7
2, 2, 6, 8
2, 2, 6, 9
2, 2, 6, 10
2, 2, 7, 7
2, 2, 7, 8
2, 2, 7, 10
2, 2, 8, 8
2, 2, 8, 9
2, 2, 8, 10
2, 2, 9, 10
2, 2, 10, 10
2, 3, 3, 3
2, 3, 3, 5
2, 3, 3, 6
2, 3, 3, 7
2, 3, 3, 8
2, 3, 3, 9
2, 3, 3, 10
2, 3, 4, 4
2, 3, 4, 5
2, 3, 4, 6
2, 3, 4, 7
2, 3, 4, 8
2, 3, 4, 9
2, 3, 4, 10
2, 3, 5, 5
2, 3, 5, 6
2, 3, 5, 7
2, 3, 5, 8
2, 3, 5, 9
2, 3, 5, 10
2, 3, 6, 6
2, 3, 6, 7
2, 3, 6, 8
2, 3, 6, 9
2, 3, 6, 10
2, 3, 7, 7
2, 3, 7, 8
2, 3, 7, 9
2, 3, 7, 10
2, 3, 8, 8
2, 3, 8, 9
2, 3, 8, 10
2, 3, 9, 9
2, 3, 9, 10
2, 3, 10, 10
2, 4, 4, 4
2, 4, 4, 5
2, 4, 4, 6
2, 4, 4, 7
2, 4, 4, 8
2, 4, 4, 9
2, 4, 4, 10
2, 4, 5, 5
2, 4, 5, 6
2, 4, 5, 7
2, 4, 5, 8
2, 4, 5, 9
2, 4, 5, 10
2, 4, 6, 6
2, 4, 6, 7
2, 4, 6, 8
2, 4, 6, 9
2, 4, 6, 10
2, 4, 7, 7
2, 4, 7, 8
2, 4, 7, 9
2, 4, 7, 10
2, 4, 8, 8
2, 4, 8, 9
2, 4, 8, 10
2, 4, 9, 9
2, 4, 9, 10
2, 4, 10, 10
2, 5, 5, 7
2, 5, 5, 8
2, 5, 5, 9
2, 5, 5, 10
2, 5, 6, 6
2, 5, 6, 7
2, 5, 6, 8
2, 5, 6, 9
2, 5, 6, 10
2, 5, 7, 7
2, 5, 7, 8
2, 5, 7, 9
2, 5, 7, 10
2, 5, 8, 8
2, 5, 8, 9
2, 5, 8, 10
2, 5, 9, 10
2, 5, 10, 10
2, 6, 6, 6
2, 6, 6, 7
2, 6, 6, 8
2, 6, 6, 9
2, 6, 6, 10
2, 6, 7, 8
2, 6, 7, 9
2, 6, 7, 10
2, 6, 8, 8
2, 6, 8, 9
2, 6, 8, 10
2, 6, 9, 9
2, 6, 9, 10
2, 6, 10, 10
2, 7, 7, 8
2, 7, 7, 10
2, 7, 8, 8
2, 7, 8, 9
2, 7, 9, 10
2, 7, 10, 10
2, 8, 8, 8
2, 8, 8, 9
2, 8, 8, 10
2, 8, 9, 9
2, 8, 9, 10
2, 8, 10, 10
2, 9, 10, 10
3, 3, 3, 3
3, 3, 3, 4
3, 3, 3, 5
3, 3, 3, 6
3, 3, 3, 7
3, 3, 3, 8
3, 3, 3, 9
3, 3, 3, 10
3, 3, 4, 4
3, 3, 4, 5
3, 3, 4, 6
3, 3, 4, 7
3, 3, 4, 8
3, 3, 4, 9
3, 3, 5, 5
3, 3, 5, 6
3, 3, 5, 7
3, 3, 5, 9
3, 3, 5, 10
3, 3, 6, 6
3, 3, 6, 7
3, 3, 6, 8
3, 3, 6, 9
3, 3, 6, 10
3, 3, 7, 7
3, 3, 7, 8
3, 3, 7, 9
3, 3, 8, 8
3, 3, 8, 9
3, 3, 8, 10
3, 3, 9, 9
3, 3, 9, 10
3, 4, 4, 4
3, 4, 4, 5
3, 4, 4, 6
3, 4, 4, 7
3, 4, 4, 8
3, 4, 4, 9
3, 4, 4, 10
3, 4, 5, 5
3, 4, 5, 6
3, 4, 5, 7
3, 4, 5, 8
3, 4, 5, 9
3, 4, 5, 10
3, 4, 6, 6
3, 4, 6, 8
3, 4, 6, 9
3, 4, 6, 10
3, 4, 7, 7
3, 4, 7, 8
3, 4, 7, 9
3, 4, 7, 10
3, 4, 8, 9
3, 4, 8, 10
3, 4, 9, 9
3, 4, 10, 10
3, 5, 5, 6
3, 5, 5, 7
3, 5, 5, 8
3, 5, 5, 9
3, 5, 6, 6
3, 5, 6, 7
3, 5, 6, 8
3, 5, 6, 9
3, 5, 6, 10
3, 5, 7, 8
3, 5, 7, 9
3, 5, 7, 10
3, 5, 8, 8
3, 5, 8, 9
3, 5, 9, 9
3, 5, 9, 10
3, 5, 10, 10
3, 6, 6, 6
3, 6, 6, 7
3, 6, 6, 8
3, 6, 6, 9
3, 6, 6, 10
3, 6, 7, 7
3, 6, 7, 8
3, 6, 7, 9
3, 6, 7, 10
3, 6, 8, 8
3, 6, 8, 9
3, 6, 8, 10
3, 6, 9, 9
3, 6, 9, 10
3, 6, 10, 10
3, 7, 7, 7
3, 7, 7, 8
3, 7, 7, 9
3, 7, 7, 10
3, 7, 8, 8
3, 7, 8, 9
3, 7, 9, 9
3, 7, 9, 10
3, 7, 10, 10
3, 8, 8, 8
3, 8, 8, 9
3, 8, 8, 10
3, 8, 9, 9
3, 8, 9, 10
3, 8, 10, 10
3, 9, 9, 9
3, 9, 9, 10
3, 9, 10, 10
4, 4, 4, 4
4, 4, 4, 5
4, 4, 4, 6
4, 4, 4, 7
4, 4, 4, 8
4, 4, 4, 9
4, 4, 4, 10
4, 4, 5, 5
4, 4, 5, 6
4, 4, 5, 7
4, 4, 5, 8
4, 4, 5, 10
4, 4, 6, 8
4, 4, 6, 9
4, 4, 6, 10
4, 4, 7, 7
4, 4, 7, 8
4, 4, 7, 9
4, 4, 7, 10
4, 4, 8, 8
4, 4, 8, 9
4, 4, 8, 10
4, 4, 10, 10
4, 5, 5, 5
4, 5, 5, 6
4, 5, 5, 7
4, 5, 5, 8
4, 5, 5, 9
4, 5, 5, 10
4, 5, 6, 6
4, 5, 6, 7
4, 5, 6, 8
4, 5, 6, 9
4, 5, 6, 10
4, 5, 7, 7
4, 5, 7, 8
4, 5, 7, 9
4, 5, 7, 10
4, 5, 8, 8
4, 5, 8, 9
4, 5, 8, 10
4, 5, 9, 9
4, 5, 9, 10
4, 5, 10, 10
4, 6, 6, 6
4, 6, 6, 7
4, 6, 6, 8
4, 6, 6, 9
4, 6, 6, 10
4, 6, 7, 7
4, 6, 7, 8
4, 6, 7, 9
4, 6, 7, 10
4, 6, 8, 8
4, 6, 8, 9
4, 6, 8, 10
4, 6, 9, 9
4, 6, 9, 10
4, 6, 10, 10
4, 7, 7, 7
4, 7, 7, 8
4, 7, 8, 8
4, 7, 8, 9
4, 7, 8, 10
4, 7, 9, 9
4, 7, 9, 10
4, 7, 10, 10
4, 8, 8, 8
4, 8, 8, 9
4, 8, 8, 10
4, 8, 9, 9
4, 8, 9, 10
4, 8, 10, 10
4, 9, 9, 10
5, 5, 5, 5
5, 5, 5, 6
5, 5, 5, 9
5, 5, 6, 6
5, 5, 6, 7
5, 5, 6, 8
5, 5, 7, 7
5, 5, 7, 8
5, 5, 7, 10
5, 5, 8, 8
5, 5, 8, 9
5, 5, 8, 10
5, 5, 9, 9
5, 5, 9, 10
5, 5, 10, 10
5, 6, 6, 6
5, 6, 6, 7
5, 6, 6, 8
5, 6, 6, 9
5, 6, 6, 10
5, 6, 7, 7
5, 6, 7, 8
5, 6, 7, 9
5, 6, 8, 8
5, 6, 8, 9
5, 6, 8, 10
5, 6, 9, 9
5, 6, 9, 10
5, 6, 10, 10
5, 7, 7, 9
5, 7, 7, 10
5, 7, 8, 8
5, 7, 8, 9
5, 7, 8, 10
5, 7, 9, 10
5, 7, 10, 10
5, 8, 8, 8
5, 8, 8, 9
5, 8, 8, 10
5, 9, 10, 10
6, 6, 6, 6
6, 6, 6, 8
6, 6, 6, 9
6, 6, 6, 10
6, 6, 7, 9
6, 6, 7, 10
6, 6, 8, 8
6, 6, 8, 9
6, 6, 8, 10
6, 6, 9, 10
6, 7, 7, 10
6, 7, 8, 9
6, 7, 8, 10
6, 7, 9, 9
6, 7, 10, 10
6, 8, 8, 8
6, 8, 8, 9
6, 8, 8, 10
6, 8, 9, 9
6, 8, 9, 10
6, 9, 9, 10
6, 10, 10, 10
7, 7, 9, 10
7, 8, 8, 9
7, 8, 8, 10
7, 8, 9, 10
7, 8, 10, 10
8, 8, 8, 10