365. Water and Jug Problem

T: O(j1+j2)

S: O(j1+j2)

```java
class Solution {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        int j1 = Math.min(jug1Capacity, jug2Capacity);
        int j2 = Math.max(jug1Capacity, jug2Capacity);

        boolean[] visited = new boolean[j1+j2+1];
        return dfs(j1, j2, visited, targetCapacity, 0);

    }
    private boolean dfs(int j1, int j2, boolean[] visited, int targetCapacity, int current) {
        if (current == targetCapacity) {
            return true;
        }
        if (visited[current]) {
            return false;
        }
        visited[current] = true;

        /**
        current 水量 分成三個區間

           ----j1----j2---- 


        */
        if (current <= j1) {
            return dfs(j1, j2, visited, targetCapacity, 0) || // 倒掉 j1
                dfs(j1, j2, visited, targetCapacity, j1) || // 裝滿到j1
                dfs(j1, j2, visited, targetCapacity, j2) || // 裝滿到j2
                dfs(j1, j2, visited, targetCapacity, current + j2) || //水在 j1(so current <= j1), 把j2 裝滿
                dfs(j1, j2, visited, targetCapacity, current + j1); //水在 j2(current <= j1), 把 j1 裝滿
        } else if (current <= j2) {
            return dfs(j1, j2, visited, targetCapacity, 0) || // 倒掉 j2
                dfs(j1, j2, visited, targetCapacity, current - j1) || // 水在 j1 and j2, 倒掉 j1
                dfs(j1, j2, visited, targetCapacity, j2); // 水都在 j2, 裝滿 j2
        } else {
            return dfs(j1, j2, visited, targetCapacity, 0) || // 全部倒掉
                dfs(j1, j2, visited, targetCapacity, current - j1) || // 倒掉 j1
                dfs(j1, j2, visited, targetCapacity, current - j2); // 倒掉 j2
        }
    }
}
```

refer this later:

https://leetcode.com/problems/water-and-jug-problem/solutions/3290210/python-dfs-bfs-complexity-analysis-video-explanation/