题目描述

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

示例

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24

输入: [1, 2, 1, 2]
输出: False

代码

public class 二十四点游戏 {
    static final int GOAL = 24;
    static final double INFINITESIMAL = 1e-6; // 无穷小量
    static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
    static final int CARD_SIZE = 4;

    public boolean judgePoint24(int[] nums) {
       List<Double> list = new ArrayList<>();
        for (int num : nums) {
            list.add((double) num);
        }
        return solve(list);
    }

    public boolean solve(List<Double> list) {
        // 当列表中没有元素的时候，直接返回
        if (list.size() == 0)
            return false;
        // 当列表中的元素只剩下一个元素的时候，说明算法运算已经到了最后一步了
        // 可以判断一下是否与目标结果相等
        if (list.size() == 1)
            return Math.abs(list.get(0) - GOAL) < INFINITESIMAL;
        int size = list.size();

        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                if (i != j) { // 当 i 不等于 j的时候，代表选中了两个数字
                    List<Double> newList = new ArrayList<>();
                    // 将不是选中的数字放进newList里
                    for (int k = 0; k < list.size(); ++k) {
                        if(i != k && j != k) {
                            newList.add(list.get(k));
                        }
                    }
                    // 进行加减乘除的操作
                    for (int z = 0; z < CARD_SIZE; ++z) {
                        // 加法或乘法，数字调换位置得到的是一样的结果，可以不重复操作
                        if (2 > z && i > j)
                            continue;
                        if (ADD == z) {
                            newList.add(list.get(i) + list.get(j));
                        } else if (MULTIPLY == z) {
                            newList.add(list.get(i) * list.get(j));
                        } else if (SUBTRACT == z) {
                            newList.add(list.get(i) - list.get(j));
                        } else if(DIVIDE == z) {
                            if (Math.abs(list.get(j)) < INFINITESIMAL)
                                continue;
                            newList.add(list.get(i) / list.get(j));
                        }
                        if (solve(newList))
                            return true;
                        // 如果这样选不行，于是移除出来，重新选
                        newList.remove(newList.size() - 1);
                    }
                }
            }
        }
        // 所有结果都没有结果，返回false
        return false;
    }


    public static void main(String[] args) {
        int[] nums = {4,1,8,7};
        int[] nums2 = {1,3,2,6};
        二十四点游戏 test = new 二十四点游戏();
        boolean b1 = test.judgePoint24(nums);
        boolean b2 = test.judgePoint24(nums2);
        System.out.println(b1);
        System.out.println(b2);

    }



}

思路

1. 这题的标签是深度优先，根据这个出发，我们便可知道用回溯法。

2. 于是可以根据回溯法的算法架构，定义一个用来回溯的solve方法，并在开始的方法中调用。

3. 接下来看回溯方式和约束条件，已知有4个数以及3个运算符，想到的方法是将4个数化简成三个数，然后将三个数来化简成2个数，最后到一个数的时候，便可以对结果进行判断。

4. 于是我们可以定义两个list（list和newList），分别存放未化简数字前和化简数字后。

5. 化简的方式是从传入solve的list中抽取两个数字（本例中采用了两个循环来抽取）进行加减乘除后的结果放进newList中，当然，在这之前没选中的自然也会添加进newList。

6. 设置终止条件，就是当list的size等于一的时候，对这个结果与目标结果进行判断，看是否在误差范围之内。如果是则返回true，否则返回false。

7. 当次轮回溯未满足条件的时候，将最后加进newList的结果取出，代表回溯到上一层。

8. 如果所有可能都执行完了，也没有返回true，则返回false。

9. 详细的一些细节优化处理见代码。