679. 24 Game

679. 24 Game

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: 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.

--------------------------
排列组合。任取2个数，对它们进行四则运算，然后放回数组。直到数组大小为1
注意：这种方法可以处理掉括号
follow up
#1 打印出所有答案：开一个额外的数组作为参数记录（见下）
#2 如果括号不让用：应该是更简单。把所有排列组合写出来，然后写一个evaluate方法来计算。

class Solution {
    public boolean judgePoint24(int[] nums) {
        List<Double> l = new ArrayList<>();
        for (int i : nums) {
            l.add((double) i);
        }
        return helper(l);
    }
    
    private boolean helper(List<Double> nums) {
        if (nums.size() == 1) {            
            if (Math.abs(nums.get(0) - 24.0) < 1e-6) {
                return true;   
            }
            return false;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i == j || nums.get(i) == nums.get(j)) continue;
                
                List<Double> tmp = new ArrayList<>();
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) tmp.add(nums.get(k));
                }
                
                double n1 = nums.get(i);
                double n2 = nums.get(j);
                for (int k = 0; k < 4; k++) {
                    double val = 0;
                    if (k < 2 && j < i) continue;
                    if (k == 0) val = n1 + n2;
                    if (k == 1) val = n1 * n2;
                    if (k == 2) val = n1 - n2;
                    if (k == 3) {
                        if (n2 != 0) val = n1 / n2;
                        else continue;
                    }
                    
                    tmp.add(val);
                    if (helper(tmp)) return true;
                    tmp.remove(tmp.size() - 1);
                }
            }
        }
        
        return false;
    }
}

Follow #1 打印出所有答案
额外的数组里存的是为被计算前的值，如 “(1+3)”。对应原来的数组存的是4.

 public static boolean judgePoint24(int[] nums) {
        List<Double> l = new ArrayList<>();
        List<String> s = new ArrayList<>();
        for (int i : nums) {
            l.add((double) i);
            s.add(Integer.toString(i));
        }

        List<String> rt = new ArrayList<>();
        helper(l, s, rt);

        for (String ss : rt) {
            System.out.println(ss);
        }
        return true;
    }

    private static void helper(List<Double> nums, List<String> s, List<String> rt) {
        if (nums.size() == 1) {
            if (Math.abs(nums.get(0) - 24.0) < 1e-6) {
                rt.add(s.get(0));
            }
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i == j || nums.get(i) == nums.get(j)) continue;

                List<Double> tmp = new ArrayList<>();
                List<String> tmpS = new ArrayList<>();
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) {
                        tmp.add(nums.get(k));
                        tmpS.add(s.get(k));
                    }
                }

                double n1 = nums.get(i);
                double n2 = nums.get(j);
                for (int k = 0; k < 4; k++) {
                    double val = 0;
                    String ss = "";
                    if (k < 2 && j < i) continue;
                    if (k == 0) {
                        val = n1 + n2;
                        ss = "(" + s.get(i) + "+" + s.get(j) + ")";
                    }
                    if (k == 1) {
                        val = n1 * n2;
                        ss = "(" + s.get(i) + "*" + s.get(j) + ")";
                    }
                    if (k == 2) {
                        val = n1 - n2;
                        ss = "(" + s.get(i) + "-" + s.get(j) + ")";
                    }
                    if (k == 3) {
                        if (n2 != 0) {
                            val = n1 / n2;
                            ss = "(" + s.get(i) + "/" + s.get(j) + ")";
                        }
                        else continue;
                    }

                    tmp.add(val);
                    tmpS.add(ss);
                    helper(tmp, tmpS, rt);
                    tmp.remove(tmp.size() - 1);
                    tmpS.remove(tmpS.size() - 1);
                }
            }
        }

        return;
    }