# Python with explanation - Generate All Possibilities

1. Use `itertools.permutations` to generate all the possible operands and operators to form an array of length 7, representing an equation of 4 operands and 3 operators.
2. The `possible` function tries to evaluate the equation with different combinations of brackets, terminating as soon as an equation evaluates to 24. Each time `evaluate` is called, it reduces the length of the equation by 2, as it takes a triplet (operand, operator, operand) and evaluates into a value.
3. Compare the final result of the equation with a small delta because of floating point inaccuracies.

- Yangshun

``````class Solution(object):
def judgePoint24(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
import itertools
TARGET = 24
EQN_LEN = 3 # (Operand, Operator, Operand) triplet.
# Generate all possible number sequences. Convert to float string so that
# division does not result in truncation.
number_orders = set(tuple(itertools.permutations([str(num) + '.0' for num in nums])))
# Generate all possible operator sequences.
operator_orders = set(tuple(itertools.permutations('***///+++---', len(nums) - 1)))

# Evaluate an equation with different permutation of brackets
# and return True if any of them evaluate to the target.
def possible(equation):
found = [False]
def evaluate(eqn):
# Reduces an equation by length 2 each time:
# An equation of ['1.0', '*', '2.0', '+', '3.0', '/', '4.0'] becomes:
# - [2.0', '+', '3.0', '/', '4.0'] (1.0 * 2.0 reduced to 2.0)
# - [1.0', '*', '5.0', '/', '4.0'] (2.0 + 3.0 reduced to 5.0)
# - [1.0', '*', '2.0', '+', '0.75'] (3.0 / 4.0 reduced to 0.75)
if found[0]:
return
if len(eqn) == EQN_LEN:
val = eval(''.join(eqn))
# Compare against a delta because of floating point inaccuracies.
if abs(val - TARGET) < 0.0001:
found[0] = True
return
# Recursively try different permutations
# of operands + operators triplets, simulating brackets.
for i in range(0, len(eqn) - 1, 2):
try:
# Wrap in try/except as there can be a division by 0 error.
evaluate(eqn[:i] + [str(eval(''.join(eqn[i:i + EQN_LEN])))] + eqn[i + EQN_LEN:])
except:
pass
evaluate(equation)
return found[0]

for number_order in number_orders:
for operator_order in operator_orders:
equation = [None] * (len(number_order) + len(operator_order))
for i, number in enumerate(number_order):
equation[0 + i * 2] = number
for i, operator in enumerate(operator_order):
equation[1 + i * 2] = operator
# Generate an equation to test whether it is possible to get 24 using it.
# Example equation: ['1.0', '*', '2.0', '+', '3.0', '/', '4.0']
if possible(equation):
return True
return False
``````

• @yangshun Nice solution with some really good explanation in comments. DFS didn't come to my mind at first when I saw the question, now it makes sense. Thanks for posting it.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.