2022-04-23£º¸ø¶¨Ò»¸ö³¤¶ÈΪ4µÄÕûÊýÊý×é cards ¡£

package main

import "fmt"

func main() {
	cards := []int{1, 1, 3, 4}
	ret := judgePoint24(cards)
	fmt.Println(ret)
}

func judgePoint24(cards []int) bool {
	if len(cards) == 0 {
		return false
	}
	n := len(cards)
	arr := make([]*Number, n)
	for i := 0; i < n; i++ {
		arr[i] = NewNumber(cards[i], 1)
	}
	return judge(arr, len(cards))
}

// arrÖУ¬ÓÐЧµÄ·¶Î§arr[0...size-1] ... ÔÙÍùÓÒ£¬¶¼ÎÞЧÁË£¬²»Óÿ´ÁË£¡
func judge(arr []*Number, size int) bool {
	if size == 1 {
		return arr[0].numerator == 24 && arr[0].denominator == 1
	}
	for i := 0; i < size; i++ {
		for j := i + 1; j < size; j++ {
			inum := arr[i]
			jnum := arr[j]
			arr[j] = arr[size-1]
			arr[i] = add(inum, jnum)
			if judge(arr, size-1) {
				return true
			}
			arr[i] = minus(inum, jnum)
			if judge(arr, size-1) {
				return true
			}
			arr[i] = minus(jnum, inum)
			if judge(arr, size-1) {
				return true
			}
			arr[i] = multiply(inum, jnum)
			if judge(arr, size-1) {
				return true
			}
			arr[i] = divide(inum, jnum)
			if arr[i] != nil && judge(arr, size-1) {
				return true
			}
			arr[i] = divide(jnum, inum)
			if arr[i] != nil && judge(arr, size-1) {
				return true
			}
			arr[i] = inum
			arr[j] = jnum
		}
	}
	return false
}

type Number struct {
	numerator   int
	denominator int
}

func NewNumber(n, d int) *Number {
	ans := new(Number)
	ans.numerator = n
	ans.denominator = d
	return ans
}

func add(a, b *Number) *Number {
	return simple(a.numerator*b.denominator+b.numerator*a.denominator, a.denominator*b.denominator)
}

func minus(a, b *Number) *Number {
	return simple(a.numerator*b.denominator-b.numerator*a.denominator, a.denominator*b.denominator)
}

func multiply(a, b *Number) *Number {
	return simple(a.numerator*b.numerator, a.denominator*b.denominator)
}

func divide(a, b *Number) *Number {
	if b.numerator == 0 {
		return nil
	} else {
		return simple(a.numerator*b.denominator, a.denominator*b.numerator)
	}
}

func simple(up, down int) *Number {
	if up == 0 {
		return NewNumber(0, 1)
	}
	gcd0 := abs(gcd(up, down))
	return NewNumber(up/gcd0, down/gcd0)
}

func abs(a int) int {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	} else {
		return gcd(b, a%b)
	}
}