题解 | #24点游戏算法#

package org.example.test.practice;

import com.alibaba.fastjson.JSONObject;

import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Scanner;

public class Main {

static boolean[] vis;
static LinkedList<Integer> path = new LinkedList<>();
static boolean ans;

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNextInt()) {
        int[] num = new int[4];
        for (int i = 0; i < 4; i++) {
            num[i] = scanner.nextInt();
        }
        Arrays.sort(num);
        vis = new boolean[4];
        ans = false;
        dfs(num, 0);
        System.out.println(ans);
    }

}

/**
 * 回溯算法
 *
 * @param num
 * @param target
 */
private static void dfs(int[] num, int target) {
    if (path.size() == num.length && target == 24) {
        ans = true;
        System.out.println(JSONObject.toJSONString(path));
        return;
    }
    for (int i = 0; i < num.length; i++) {
        if (vis[i] || i > 0 && num[i - 1] == num[i] && !vis[i - 1]) {
            continue;
        }
        vis[i] = true;
        path.add(num[i]);
        if (path.size() == 1) { // 很重要
            dfs(num, num[i]);
        } else if (path.size() > 1) {
            dfs(num, target - num[i]);
            dfs(num, target + num[i]);
            dfs(num, target * num[i]);
            if (target % num[i] == 0) // 很重要
                dfs(num, target / num[i]);
        }
        path.removeLast();
        vis[i] = false;
    }
}

}