-
Notifications
You must be signed in to change notification settings - Fork 0
/
679.24_game.go
62 lines (51 loc) · 1.22 KB
/
679.24_game.go
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
package backtracking
import "math"
/*
679. 24 Game
https://leetcode.com/problems/24-game/
*/
var epsilon = math.Pow10(-6)
func judgePoint24(cards []int) bool {
generateAllPossibleResults := func(a, b float64) []float64 {
res := [] float64 {a+b, a*b, a-b, b-a}
if b != 0 {res = append(res, a/b) }
if a != 0 {res = append(res, b/a) }
return res
}
isValid := func(a []float64) bool {
return math.Abs(a[0] - 24) <= epsilon
}
cardsWithoutIndexes := func(a []float64, index1, index2 int) []float64 {
r := []float64{}
for i, v := range a {
if i != index1 && i != index2 {
r = append(r, v)
}
}
return r
}
var backtrack func(a []float64) bool
backtrack = func(a []float64) bool {
l := len(a)
if l == 1 { return isValid(a) }
for i:=0; i<l;i++ {
for j:=i+1; j<l; j++ {
possibleResults := generateAllPossibleResults(a[i], a[j])
for _,v := range possibleResults {
newA := cardsWithoutIndexes(a, i, j)
newA = append(newA, v)
if backtrack(newA) { return true }
}
}
}
return false
}
fCards := []float64{}
for _,v := range cards {
fCards = append(fCards, float64(v))
}
return backtrack(fCards)
}
func JudgePoint24(cards []int) bool {
return judgePoint24(cards)
}