leetcode-go/hard/679.24-game.go

const eps = 0.000001

func judgePoint24(nums []int) bool {
	list := make([]float64, len(nums))
	for i := range nums {
		list[i] = float64(nums[i])
	}
	return dfs(list)
}

func dfs(nums []float64) bool {
	l := len(nums)
	if l == 1 && math.Abs(nums[0]-24.0) <= eps {
		return true
	}
	for i := 0; i < l-1; i++ {
		for j := i + 1; j < l; j++ {
			next := make([]float64, l-2)
			for k, idx := 0, 0; k < l; k++ {
				if k == i || k == j {
					continue
				}
				next[idx], idx = nums[k], idx+1
			}
			p, q := nums[i], nums[j]
			tmp := []float64{p + q, p - q, q - p, p * q}
			if eps <= q {
				tmp = append(tmp, p/q)
			}
			if eps <= p {
				tmp = append(tmp, q/p)
			}
			for _, t := range tmp {
				next = append(next, t)
				if dfs(next) {
					return true
				}
				next = next[:len(next)-1]
			}
		}
	}
	return false
}