# How do I make this Python solution fast enough for OJ?

• ``````	def canMeasureWater(self, x, y, z):
if not z or z in (x,y,x+y): return True
checked = {(0,0)}
queue = [(x,0),(0,y)]
def check(a,b):
if (a,b) not in checked:
queue.append((a,b))
return a + b == z
while queue:
a,b = queue.pop(0)
possibilities = [
(0, b), # pour out jug 1
(x, b), # fill jug 1
(a, 0), # pour out jug 2
(a, y), # fill jug 2
(max(0, a-(y-b)), min(y, b+a)), # pour jug 1 into jug 2
(min(x, a+b), max(0, b-(x-a))) # pour jug 2 into jug 1
]
if any([check(pa,pb) for pa, pb in possibilities]): return True
return False
``````

The idea is to do a DFS on each combination of the amount of water in the jugs. It passes test cases for small numbers but gets TLE on larger ones.

• maybe you could exclude some duplicate issue.
if current state is (0,b), the next step can't be:
empty jug 1
empty jug 2
fill jug2
pour jug 1 in to jug 2

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