679 24 Game

679. 24 Game

1. Question

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 - 1is 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. Implementation

(1) Backtracking

class Solution {
    final double epsilon = 0.0001;
    public boolean judgePoint24(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }

        List<Double> list = new ArrayList();
        for (int num : nums) {
            list.add((double) num);
        }

        return getPoint24(list);
    }

    public boolean getPoint24(List<Double> nums) {
        if (nums.size() == 0) {
            return false;
        }

        if (nums.size() == 1) {
            if (Math.abs(nums.get(0) - 24) < epsilon) {
                return true;
            }
        }

        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                double num1 = nums.get(i);
                double num2 = nums.get(j);

                if (num1 == 0 || num2 == 0) {
                    continue;
                }

                // i is greater than j, so removing element at i won't effect the position of nums.get(j)
                nums.remove(i);
                nums.remove(j);

                for (double nextNum : compute(num1, num2)) {
                    nums.add(nextNum);

                    if (getPoint24(nums)) {
                        return true;
                    }
                    nums.remove(nums.size() - 1);
                }

                nums.add(j, num2);
                nums.add(i, num1);
            }
        }
        return false;
    }

    public double[] compute(double num1, double num2) {
        return new double[] {num1 + num2, num1 - num2, num2 - num1, num1 * num2, num1 / num2, num2 / num1};
    }
}

3. Time & Space Complexity

Backtracking: 时间复杂度O(1) ? 空间复杂度O(1)?