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:
1
Input: [4, 1, 8, 7]
2
3
Output: True
4
5
Explanation: (8-4) * (7-1) = 24
Copied!
Example 2:
1
Input: [1, 2, 1, 2]
2
3
Output: False
Copied!
Note:
  1. 1.
    The division operator/represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
  2. 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. 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
1
class Solution {
2
final double epsilon = 0.0001;
3
public boolean judgePoint24(int[] nums) {
4
if (nums == null || nums.length < 4) {
5
return false;
6
}
7
8
List<Double> list = new ArrayList();
9
for (int num : nums) {
10
list.add((double) num);
11
}
12
13
return getPoint24(list);
14
}
15
16
public boolean getPoint24(List<Double> nums) {
17
if (nums.size() == 0) {
18
return false;
19
}
20
21
if (nums.size() == 1) {
22
if (Math.abs(nums.get(0) - 24) < epsilon) {
23
return true;
24
}
25
}
26
27
for (int i = 1; i < nums.size(); i++) {
28
for (int j = 0; j < i; j++) {
29
double num1 = nums.get(i);
30
double num2 = nums.get(j);
31
32
if (num1 == 0 || num2 == 0) {
33
continue;
34
}
35
36
// i is greater than j, so removing element at i won't effect the position of nums.get(j)
37
nums.remove(i);
38
nums.remove(j);
39
40
for (double nextNum : compute(num1, num2)) {
41
nums.add(nextNum);
42
43
if (getPoint24(nums)) {
44
return true;
45
}
46
nums.remove(nums.size() - 1);
47
}
48
49
nums.add(j, num2);
50
nums.add(i, num1);
51
}
52
}
53
return false;
54
}
55
56
public double[] compute(double num1, double num2) {
57
return new double[] {num1 + num2, num1 - num2, num2 - num1, num1 * num2, num1 / num2, num2 / num1};
58
}
59
}
Copied!

3. Time & Space Complexity

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