1
class Solution {
2
 public:
3
  bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
4
    if (targetCapacity > jug1Capacity + jug2Capacity) return false;
5

6
    vector<int> dp(jug1Capacity + jug2Capacity + 1, -1);
7
    return helper(0, jug1Capacity, jug2Capacity, targetCapacity, dp);
8
  }
9

10
  bool helper(int tmp, int &jug1Capacity, int &jug2Capacity, int &targetCapacity, vector<int> &dp) {
11
    if (tmp < 0 || tmp > jug1Capacity + jug2Capacity) return false;
12

13
    if (tmp == targetCapacity) return true;
14

15
    if (dp[tmp] != -1) return dp[tmp];
16

17
    dp[tmp] = false;
18
    if (helper(tmp + jug1Capacity, jug1Capacity, jug2Capacity, targetCapacity, dp))
19
      return dp[tmp] = true;
20

21
    if (helper(tmp - jug1Capacity, jug1Capacity, jug2Capacity, targetCapacity, dp))
22
      return dp[tmp] = true;
23

24
    if (helper(tmp + jug2Capacity, jug1Capacity, jug2Capacity, targetCapacity, dp))
25
      return dp[tmp] = true;
26

27
    if (helper(tmp - jug2Capacity, jug1Capacity, jug2Capacity, targetCapacity, dp))
28
      return dp[tmp] = true;
29

30
    return dp[tmp] = false;
31
  }
32
};