题解 | #24点游戏算法#

深度优先visited标记的顺序问题：

• 进入递归前标记（无需传入遍历到的idx）
• 进入递归后标记（减少外部代码，但是需要传递参数，即需要标记的idx）

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static short[] nums;
    static boolean[] visited;
    public static boolean is24(float curNum, int level){

        if(level==4) return curNum==24;

        for(int i=0;i<4;i++){
            if(!visited[i]){
                visited[i] = true;
                boolean flag = is24(curNum+nums[i],level+1)
                        || is24(curNum-nums[i],level+1)
                        || is24(curNum*nums[i],level+1)
                        || is24(curNum/nums[i],level+1);
                if(flag) return true;
                visited[i] = false;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        nums = new short[4];
        visited = new boolean[4];
        for(int i=0;i<4;i++) nums[i] = in.nextShort();

        for(int i=0;i<4;i++){
            visited[i] = true;
            if(is24(nums[i], 1)){
                System.out.println(true);
                return;
            }
            visited[i] = false;
        }
        System.out.println(false);
    }
}

题解二：

import java.util.BitSet;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static short[] nums;
    static BitSet visited;
    public static boolean is24(float curNum, int preIdx){
        visited.set(preIdx);
        if(visited.cardinality()==4) {
            visited.set(preIdx,false);
            return curNum==24;
        }

        for(int i=0;i<4;i++){
            if(!visited.get(i)){
                boolean flag = is24(curNum+nums[i],i)
                        || is24(curNum-nums[i],i)
                        || is24(curNum*nums[i],i)
                        || is24(curNum/nums[i],i);
                if(flag) return true;
            }
        }
        visited.set(preIdx,false);
        return false;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        nums = new short[4];
        visited = new BitSet(4);
        for(int i=0;i<4;i++) nums[i] = in.nextShort();

        for(int i=0;i<4;i++){
            if(is24(nums[i], i)){
                System.out.println(true);
                return;
            }
        }
        System.out.println(false);
    }
}