Description

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, )to get the value of 24.

Example 1:Input: [4, 1, 8, 7]Output: TrueExplanation: (8-4) * (7-1) = 24Example 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.

思路

题意：给定四张标有数字（1-9）的卡片，问通过加减乘除和小括号组成的表达式的结果能否等于24。

题解：考虑穷举法的话，四个数字共有4！种排列方法，4个数字中间加入符号共有4x4x4种方法，最后考虑小括号，小括号的放法共有(A(B(CD))、(A((BC)D)、((AB)(CD))、((A(BC))D)、(((AB)C)D)五种，那么种类最多有4！x4^3x5 = 7680种。

考虑回溯法，首先我们从集合A = {1 、2、3、4}中任意取出两个数，如取1、2，那么A = A - {1、2}，对取出来的两个数字分别进行不同的四则运算，1 + 2、1 - 2……，将结果加入A中，有{3、3、4}、{-1，3，4}等，通过这种方法，将四个数降为三个数，然后降为两个数……

 Java

class Solution {    boolean res = false;    final double esp = 1e-4;    public boolean judgePoint24(int[] nums) {        List
     
      list = new ArrayList
      
       ();        for (int val:nums)  list.add((double)val);        solver(list);        return res;    }    void solver(List
       
         array){        if (res)    return;        if (array.size() == 1 && Math.abs(array.get(0) - 24.0) <= esp){            res = true;            return;        }        for (int i = 0;i < array.size();i++){            for (int j = 0;j < i;j++){                List
        
         list = new ArrayList
         
          ();                Double p1 = array.get(i),p2 = array.get(j);                list.addAll(Arrays.asList(p1+p2,p1-p2,p2-p1,p1*p2));                                //除数是否为0                if (Math.abs(p1) > esp){                    list.add(p2/p1);                }                if (Math.abs(p2) > esp){                    list.add(p1/p2);                }                array.remove(i);                array.remove(j);                for (Double val:list){                    array.add(val);                    solver(array);                    array.remove(val);                }                array.add(j,p2);                array.add(i,p1);            }        }    }}