Question

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through operators to get the value of 24.

Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: [1, 2, 1, 2]
Output: False

Note:

  1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
  2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
  3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Solutions

  • Method 1: DFS 
      class Solution {
      public boolean judgePoint24(int[] nums) {
          List<Double> list = new ArrayList<Double>();
          for(int num : nums) list.add(num * 1D);
          return dfs(list);
      }
      private boolean dfs(List<Double> list){
          int size = list.size();
          if(size == 1 && Math.abs(list.get(0) - 24) < 0.0001) return true;
          for(int i = 0; i < size; i++){
              for(int j = i + 1; j < size; j++){
                  List<Double> possibles = getPossibles(list.get(i), list.get(j));
                  for(double p : possibles){
                      List<Double> next = new ArrayList<>();
                      next.add(p);
                      for(int k = 0; k < size; k++){
                          if(k == i || k == j) continue;
                          next.add(list.get(k));
                      }
                      if(dfs(next)) return true;
                  }
              }
          }
          return false;
      }
      private List<Double> getPossibles(double a, double b){
          List<Double> result = new ArrayList<>();
          result.add(a + b);
          result.add(a * b);
          result.add(a - b);
          result.add(b - a);
          result.add(a / b);
          result.add(b / a);
          return result;
      }
  }