-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path679.24-game.cpp
More file actions
88 lines (83 loc) · 2.47 KB
/
679.24-game.cpp
File metadata and controls
88 lines (83 loc) · 2.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Tag: Array, Math, Backtracking
// Time: O(4！ * 4 ^ 3)
// Space: O(1)
// Ref: -
// Note: -
// Video: https://youtu.be/qZSvcFSpO6o
// You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.
// You are restricted with the following rules:
//
// The division operator '/' represents real division, not integer division.
//
//
// For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
//
//
// Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.
//
// For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.
//
//
// You cannot concatenate numbers together
//
// For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.
//
//
//
// Return true if you can get such expression that evaluates to 24, and false otherwise.
//
// Example 1:
//
// Input: cards = [4,1,8,7]
// Output: true
// Explanation: (8-4) * (7-1) = 24
//
// Example 2:
//
// Input: cards = [1,2,1,2]
// Output: false
//
//
// Constraints:
//
// cards.length == 4
// 1 <= cards[i] <= 9
//
//
class Solution {
public:
bool judgePoint24(vector<int>& cards) {
sort(cards.begin(), cards.end());
do {
unordered_set<double> res = dfs(cards, 0, 3);
for (auto &x: res) {
if (abs(x - 24) < 1e-9) {
return true;
}
}
} while (next_permutation(cards.begin(), cards.end()));
return false;
}
unordered_set<double> dfs(vector<int>& cards, int l, int r) {
unordered_set<double> res;
if (l == r) {
res.insert(cards[l]);
} else {
for (int m = l; m < r; m++) {
unordered_set<double> left = dfs(cards, l, m);
unordered_set<double> right = dfs(cards, m + 1, r);
for (auto &a : left) {
for (auto &b : right) {
res.insert(a + b);
res.insert(a - b);
res.insert(a * b);
if (b != 0) {
res.insert(a / b);
}
}
}
}
}
return res;
}
};