24点解法

算法之美
1

679. 24 点游戏

题目说可以加括号和±*/号。
可以用搜索，枚举出所有表达式
比如 [1,2,3,4]
先把所有排列枚举出来，
然后在一个排列中加入符号，就说可以加括号，所相当于所有符号优先级是相同的，就看你想哪个先算，所有可能都算一遍，看能不能得到24。
注意可以浮点运算注意判断24相等的方法。



func makeNumList(selected []float64, nums []int) [][]float64 {
	res := [][]float64{}
	if len(selected) == 4 {
		temp := make([]float64, 4)
		copy(temp, selected)
		res = append(res, temp)
		return res
	}

	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			continue
		}
		sn := nums[i]
		nums[i] = 0
		res = append(res, makeNumList(append(selected, float64(sn)), nums)...)
		nums[i] = sn
	}

	return res
}

func canCal24(nums []float64) bool {
	if len(nums) == 1 && math.Abs(nums[0] - 24)<1e-6 { // 浮点判断方法。
		return true
	}

	if len(nums) <= 1 {
		//fmt.Println(nums[0])
		return false
	}

	for i := 0; i < len(nums)-1; i++ { //先计算nums[i], nums[i+1]
		newNums := make([]float64, len(nums))
		copy(newNums, nums)
		newNums = append(newNums[:i+1], newNums[i+2:]...) // 计算完会少一个数
		for op := 1; op <= 4; op++ { // 添加符号
			switch op {
			case 1: // +号
				newNums[i] = nums[i] + nums[i+1]
			case 2: // -号
				newNums[i] = nums[i] - nums[i+1]
			case 3: // *号
				newNums[i] = nums[i] * nums[i+1]
			case 4: // /号
				if nums[i+1] == 0 { //非0除数
					continue
				}
				newNums[i] = nums[i] / nums[i+1]
			}
			if canCal24(newNums) {
				//fmt.Println(newNums, i, op)
				return true
			}
		}
	}

	return false
}

func judgePoint24(nums []int) bool {
	permutation := makeNumList(nil, nums)
	for _, r := range permutation {
		//fmt.Println(r)
		if canCal24(r) {
			return true
		}
	}
	//fmt.Println(len(permutation))

	return false
}