You have 4 cards each containing a number from 1 to 9.  You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.


Example 1:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24



Example 2:

Input: [1, 2, 1, 2]
Output: False



Note:

The division operator / represents real division, not integer division.  For example, 4 / (1 - 2/3) = 12.
Every operation done is between two numbers.  In particular, we cannot use - as a unary operator.  For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
You cannot concatenate numbers together.  For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics

Complete search

Starter code: class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        

Solutions:
class Solution(object):

	def judgePoint24(self, nums):
		bad = '떢븻각걎냇갅갸꺚뵟숣욄뵴뵞뤼갈갌뤔떌옊메늄숭캸긶꺛옖갍뇐쩢곴듇걯궄옕왹눞솴걃끗긬땉궿가쌀낐걄숤뺴늘걘꽸숢걂갋갃쫐꼔솾쩡쇔솿끛뤜간븺쩬웨딴옠뤛갂뵪덠놤빐옋귒늂갰갖놥궾갆옌뼘묰거갎긷낤겼'
		return chr(int(''.join(map(str, sorted(nums)))) + 42921) not in bad


class Solution:

	def judgePoint24(self, nums):
		bad = '对撒剘劥圞剜劏哱掶桺泛揋掵従剟剣彫寣污悫壛梄甏咍哲汭剤堧点卋嬞勆叛汬泐塵栋劚嚮咃宠吖剗楗囧力桻攋壯劯嗏桹劙剢剚焧啫栕炸栫栖嚲彳剛撑烃洿宋汷彲剙揁妷埻撧汢吩壙劇剭埼吕剝汣敯憇勇剥咎囻匓'
		return chr(int(''.join(map(str, sorted(nums)))) + 19968) not in bad


class Solution(object):

	def judgePoint24(self, nums):

		def cal(operands, operaters):
			for opt in operaters:
				(op2, op1) = (operands.pop(-1), operands.pop(-1))
				if opt == '+':
					ret = op1 + op2
				elif opt == '-':
					ret = op1 - op2
				elif opt == '*':
					ret = op1 * op2
				elif opt == '/' and op2 != 0:
					ret = op1 / op2
				else:
					return float('-inf')
				operands.append(ret)
			return operands[0] if abs(operands[0] - 24) > 1e-07 else 24

		def comb(arr):
			if len(arr) == 1:
				return [arr]
			ret = []
			for i in range(len(arr)):
				if i - 1 >= 0 and arr[i] == arr[i - 1]:
					continue
				for remain in comb(arr[:i] + arr[i + 1:]):
					ret.append([arr[i]] + remain)
			return ret

		def genopt(n):
			if n == 0:
				return ['']
			ret = []
			for i in '+-*/':
				for res in genopt(n - 1):
					ret.append(i + res)
			return ret
		nums.sort()
		ops = comb(nums)
		opts = genopt(3)
		for op in ops:
			for opt in opts:
				if cal(op[:], opt) == 24:
					return True

		def base(a, b):
			return set([a + b, a - b, b - a, a * b] + ([a / b] if b != 0 else []) + ([b / a] if a != 0 else []))
		for i in range(4):
			for j in range(i + 1, 4):
				(a, b) = (nums[i], nums[j])
				remain = nums[:i] + nums[i + 1:j] + nums[j + 1:4]
				for x in base(a, b):
					for y in base(remain[0], remain[1]):
						if 24 in base(x, y):
							return True
		return False


class Solution(object):

	def judgePoint24(self, nums):
		n = len(nums)
		if n == 1:
			return abs(nums[0] - 24) < 0.0001
		for i in range(n - 1):
			for j in range(i + 1, n):
				remainder = nums[:i] + nums[i + 1:j] + nums[j + 1:]
				if self.judgePoint24(remainder + [nums[i] + nums[j]]):
					return True
				if self.judgePoint24(remainder + [nums[i] - nums[j]]):
					return True
				if self.judgePoint24(remainder + [nums[j] - nums[i]]):
					return True
				if self.judgePoint24(remainder + [nums[i] * nums[j]]):
					return True
				if nums[j] != 0 and self.judgePoint24(remainder + [nums[i] / nums[j]]):
					return True
				if nums[i] != 0 and self.judgePoint24(remainder + [nums[j] / nums[i]]):
					return True
		return False