(UVA) 23 out of 5 - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1285

In order to discover if the expression yield the value of 23, we need to try all the possibilities for the five given numbers and for the three operations. Therefore, the solution below is using backtracking.


import java.io.*;
import java.util.*;

class Main {
    public static int[] numbers;
    public static HashSet<Integer> considered;
    public static boolean gotAnswer;
   
    public static void rec(int result) {
        if (considered.size() == 5) {
            if (result == 23) {
                gotAnswer = true;
            }
            return;
        }
       
        for (int i = 0; i < 5; i++) {
            if (considered.contains(i)) {
                continue;
            }
            considered.add(i);
            if (considered.size() == 1) { // no operation applied to the first number
                rec(numbers[i]);  
            }
            else {
                rec(result*numbers[i]);
                rec(result+numbers[i]);
                rec(result-numbers[i]);
            }
            considered.remove(i);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        while (sc.hasNext()) {
            int sum = 0;
            numbers = new int[5];
            for (int i = 0; i < 5; i++) {
                numbers[i] = sc.nextInt();
                sum += numbers[i];
            }
            if (sum == 0) {
                break;
            }
           
            gotAnswer = false;
            considered = new HashSet<>();
            rec(0);       
           
            if (gotAnswer) {
                System.out.println("Possible");
            }   
            else {
                System.out.println("Impossible");
            }
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}