题目：

有两个容量分别为 *x*升 和* y*升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 *z*升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 *z升 *水。
你允许：
*   装满任意一个水壶
*   清空任意一个水壶
*   从一个水壶向另外一个水壶倒水，直到装满或者倒空

**示例 1:
输入: x = 3, y = 5, z = 4
输出: True

**示例 2:**
输入: x = 2, y = 6, z = 5
输出: False</pre>

题目的理解：

起初设想的解决方式：
（1）x和y的相差，求得所有相差的值，即每一个值与所有的值相减，直到不会产生新的值。
（2）得到的所有的值进行每一个值与所有值相加，得到一个集合B。
（3）集合B去除大于x加y的值，得到集合C。
（4）判断z是否在C中。
实现为：

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        attribute = {x, y}
        pre_length = len(attribute)

        while True:
            minus_list = list(attribute)
            for i in range(pre_length):
                for j in range(i, pre_length):
                    minus = abs(minus_list[i] - minus_list[j])
                    minus_list.append(minus)

            attribute = set(minus_list)

            if pre_length == len(attribute):
                break
            else:
                pre_length = len(attribute)

        add_list = list(attribute)
        for i in range(pre_length):
            for j in range(i, pre_length):
                add = add_list[i] + add_list[j]
                add_list.append(add)

        result_list = set(add_list)

        result_list = filter(lambda s: s <= x + y, result_list)

        return z in result_list

结果是计算超时。!_! 计算量太大了。
优化了方法：
（1）记录所有存在的可能，并用x和y对值进行判断，获取新值。
（2）仅仅对新值进行判断，如果值已经计算过，直接跳过。

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if z in [0, x, y, (x + y), abs(x - y)]:
            return True

        attribute = {x, y, abs(x - y)}
        pre_length = len(attribute)
        whole_nums = list(attribute)

        while True:
            minus_list = list(attribute)
            new_set = list()
            for i in range(pre_length):
                temp = list()
                value = minus_list[i]

                if x > value:
                    temp.append(value + y)
                    if value > y:
                        new_set.append(value - y)
                        temp.append(value - y)

                    if x - value > y:
                        new_set.append(x - value + y)
                        temp.append(x - value + y)
                        temp.append(x - value + y + y)
                    else:
                        new_set.append(y - x + value)
                        temp.append(y - x + value)
                        temp.append(y - x + value + x)

                if y > value:
                    temp.append(value + x)

                    if value > x:
                        new_set.append(value - x)
                        temp.append(value - x)

                    if y - value > x:
                        new_set.append(y - value + x)
                        temp.append(y - value + x)
                        temp.append(y - value + x + x)
                    else:
                        new_set.append(x - y + value)
                        temp.append(x - y + value)
                        temp.append(x - y + value + y)

                if z in temp:
                    return True

            attribute = list(filter(lambda x: x not in whole_nums, new_set))
            whole_nums += attribute

            if 0 >= len(attribute):
                break
            else:
                pre_length = len(attribute)

        return False

但是结果还是可悲的失败了，计算超时。!_!

还是看题解吧，伤心了！！！

python实现

题解来源

解法1. 列举所有的操作的可能：

在任意一个时刻，我们可以且仅可以采取以下几种操作：

把 X 壶的水灌进 Y 壶，直至灌满或倒空；
把 Y 壶的水灌进 X 壶，直至灌满或倒空；
把 X 壶灌满；
把 Y 壶灌满；
把 X 壶倒空；
把 Y 壶倒空。

代码

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        stack = [(0, 0)]
        self.seen = set()
        while stack:
            remain_x, remain_y = stack.pop()
            if remain_x == z or remain_y == z or remain_x + remain_y == z:
                return True
            if (remain_x, remain_y) in self.seen:
                continue
            self.seen.add((remain_x, remain_y))
            # 把 X 壶灌满。
            stack.append((x, remain_y))
            # 把 Y 壶灌满。
            stack.append((remain_x, y))
            # 把 X 壶倒空。
            stack.append((0, remain_y))
            # 把 Y 壶倒空。
            stack.append((remain_x, 0))
            # 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
            stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))
            # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
            stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))
        return False

看解题思路非常的清晰易懂，将所有的可操作的步骤来一遍。

解法2. 最大公约数

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x + y < z:
            return False
        if x == 0 or y == 0:
            return z == 0 or x + y == z
        return z % math.gcd(x, y) == 0

此题目的解法满足最大公约数的问题。