Can the Water and Jug Problem always be solved with DFS alone?

DFS can explore all states, but without the GCD check and visited state tracking, it may be inefficient or enter infinite loops.

Why is the GCD important in this problem?

The target volume must be a multiple of the GCD of x and y for it to be achievable; otherwise, no sequence of fills and pours can reach it.

Should I prefer BFS or DFS for this problem?

DFS is simpler for reachability checks, while BFS is preferable if the interviewer asks for minimal operation sequences.

Does the combined water from both jugs count toward the target?

Yes, the target can be reached in either jug individually or as the sum of both jugs.

What are common mistakes when implementing this pattern?

Ignoring the GCD shortcut, forgetting to track visited states, or assuming the target must be in a single jug rather than the total.

#365

Medium

auto_awesome图·搜索

LeetCode 题解工作台

水壶问题

有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。你可以：装满任意一个水壶清空任意一个水壶将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。示例 1: 输入: x = 3,y = 5,target = 4 输出: tr…

数学深度优先搜索广度优先搜索

题目描述

有两个水壶，容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。

你可以：

装满任意一个水壶
清空任意一个水壶
将水从一个水壶倒入另一个水壶，直到接水壶已满，或倒水壶已空。

示例 1:

输入: x = 3,y = 5,target = 4
输出: true
解释：
按照以下步骤操作，以达到总共 4 升水：
1. 装满 5 升的水壶(0, 5)。
2. 把 5 升的水壶倒进 3 升的水壶，留下 2 升(3, 2)。
3. 倒空 3 升的水壶(0, 2)。
4. 把 2 升水从 5 升的水壶转移到 3 升的水壶(2, 0)。
5. 再次加满 5 升的水壶(2, 5)。
6. 从 5 升的水壶向 3 升的水壶倒水直到 3 升的水壶倒满。5 升的水壶里留下了 4 升水(3, 4)。
7. 倒空 3 升的水壶。现在，5 升的水壶里正好有 4 升水(0, 4)。
参考：来自著名的 "Die Hard"

示例 2:

输入: x = 2, y = 6, target = 5
输出: false

示例 3:

输入: x = 1, y = 2, target = 3
输出: true
解释：同时倒满两个水壶。现在两个水壶中水的总量等于 3。

提示:

1 <= x, y, target <= 10³

lightbulb

解题思路

方法一：DFS

我们不妨记 $\textit{jug1Capacity}$ 为 $x$ , $\textit{jug2Capacity}$ 为 $y$ , $\textit{targetCapacity}$ 为 $z$ 。

接下来，我们设计一个函数 $dfs(i, j)$ ，表示当前 $jug1$ 中有 $i$ 升水， $jug2$ 中有 $j$ 升水，是否可以得到 $z$ 升水。

函数 $dfs(i, j)$ 的执行过程如下：

如果 $(i, j)$ 已经被访问过，返回 $false$ 。
如果 $i = z$ 或者 $j = z$ 或者 $i + j = z$ ，返回 $true$ 。
如果我们给 $jug1$ 倒满水，或者给 $jug2$ 倒满水，或者将 $jug1$ 清空，或者将 $jug2$ 清空，可以得到 $z$ 升水，返回 $true$ 。
如果我们将 $jug1$ 中的水倒入 $jug2$ ，或者将 $jug2$ 中的水倒入 $jug1$ ，可以得到 $z$ 升水，返回 $true$ 。

答案即为 $dfs(0, 0)$ 。

时间复杂度 $O(x + y)$ ，空间复杂度 $O(x + y)$ 。其中 $x$ 和 $y$ 分别为 $\textit{jug1Capacity}$ 和 $\textit{jug2Capacity}$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        def dfs(i: int, j: int) -> bool:
            if (i, j) in vis:
                return False
            vis.add((i, j))
            if i == z or j == z or i + j == z:
                return True
            if dfs(x, j) or dfs(i, y) or dfs(0, j) or dfs(i, 0):
                return True
            a = min(i, y - j)
            b = min(j, x - i)
            return dfs(i - a, j + a) or dfs(i + b, j - b)

        vis = set()
        return dfs(0, 0)

speed

复杂度分析

指标	值
时间	and space complexity depend on the approach: the DFS/BFS can explore up to O(x*y) unique jug states, while the GCD method runs in constant time O(log(min(x,y))). Using state pruning reduces unnecessary recursion and queue expansions.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They may hint at mathematical properties like GCD to optimize the solution.
question_mark
Expect questions on avoiding infinite loops when simulating jug operations.
question_mark
They often check understanding of BFS vs DFS trade-offs in state exploration.

warning

常见陷阱

外企场景

error
Failing to check the GCD condition and running full DFS unnecessarily.
error
Not marking visited states, causing infinite recursion or repeated computations.
error
Assuming the target must be in a single jug instead of the total combined water.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the minimum number of steps to reach the target liters using BFS.
arrow_right_alt
Allow fractional jug capacities and target values to test floating-point handling.
arrow_right_alt
Generalize to three or more jugs with arbitrary capacities and target liters.

help

常见问题

外企场景

继续练习

#672 灯泡开关 Ⅱ #399 除法求值 #329 矩阵中的最长递增路径