# 679 24 Game

## 679. [24 Game](https://leetcode.com/problems/24-game/description/)

## 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 - 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. Implementation

**(1) Backtracking**

```java
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)?