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

``````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) {
}

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)) {

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

}
}
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)?

Last updated