题解 | #24点游戏算法#

import java.io.*;

/*
    知识点：递归、深度优先搜索、回溯算法
*/
public class Main {
    static boolean[] visit = new boolean[4]; // 存放对应位置数字的使用状态（1代表已使用）
	static int[] nums = new int[4]; // 存放数字

	/*
	 * 知识点：递归、深度优先搜索、回溯算法
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		while ((str = br.readLine()) != null) {
			String[] numstr = str.split(" ");
			boolean flag = false;
			for (int i = 0; i < 4; i++) {
				nums[i] = Integer.parseInt(numstr[i]); // 读取数字
			}
			System.out.println(isBingGo(0));
		}
	}

	public static boolean isBingGo(int curResult) {

		if (curResult == 24) {
			return true;
		}

		for (int i = 0; i < nums.length; i++) {
			// 已经被用了
			if (visit[i]) {

				// 如果i==length 证明是最后一轮,直接退出,并且把
				continue;
			} else {
				// 标记该数被用了
				visit[i] = true;
				boolean result = false;
				result = isBingGo(curResult + nums[i]);
				result = result || isBingGo(curResult - nums[i]);
				result = result || isBingGo(curResult * nums[i]);
				// 能除尽才能 除,否则得到的数据不准确
				if (curResult % nums[i] == 0) {
					result = result || isBingGo(curResult / nums[i]);
				}
				if (result == true) {
					return result;
				}
				// 退栈
				visit[i] = false;

			}

		}

		return false;

	}
}

这道题的难点就是回溯算法的编写,

1\怎么标记这个变量已经使用过

2\需要对数据进行四次四则运算