<p>You are given two jugs with capacities <code>x</code> liters and <code>y</code> liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach <code>target</code> using the following operations:</p>

<ul>
	<li>Fill either jug completely with water.</li>
	<li>Completely empty either jug.</li>
	<li>Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> x = 3, y = 5, target = 4 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> true </span></p>

<p><strong>Explanation:</strong></p>

<p>Follow these steps to reach a total of 4 liters:</p>

<ol>
	<li>Fill the 5-liter jug (0, 5).</li>
	<li>Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).</li>
	<li>Empty the 3-liter jug (0, 2).</li>
	<li>Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).</li>
	<li>Fill the 5-liter jug again (2, 5).</li>
	<li>Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).</li>
	<li>Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).</li>
</ol>

<p>Reference: The <a href="https://www.youtube.com/watch?v=BVtQNK_ZUJg&amp;ab_channel=notnek01" target="_blank">Die Hard</a> example.</p>
</div>

<p><strong class="example">Example 2: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> x = 2, y = 6, target = 5 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> false </span></p>
</div>

<p><strong class="example">Example 3: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> x = 1, y = 2, target = 3 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> true </span></p>

<p><strong>Explanation:</strong> Fill both jugs. The total amount of water in both jugs is equal to 3 now.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= x, y, target&nbsp;&lt;= 10<sup>3</sup></code></li>
</ul>

class Solution {
    int c1;
    int c2;
    int t;
    int **dp;
public:
    bool rec(int l1, int l2) {
        if(l1 +l2==t ) // the total amount of water in both jugs reached target
            return true;
        if(dp[l1][l2]!=-1)
            return dp[l1][l2];
        /*Below line is very important, it avoids same state infinite loop
         We temporirily makr this state as visited by marking it false, 
         later we evaluate the correct val for this state and assign at the end*/
        dp[l1][l2] = false;// We mark this state as false to avoid same-state infinite loop
        bool result=false;
        result= result | rec(l1,0);     // empty jug2
        result= result | rec(0, l2);    // empty jug1
        result= result | rec(c1, l2);   // Fill jug1
        result= result | rec(l1, c2);   // Fill jug2
        if(c2-l2 <= l1)     // jug2 can be made full by pouring from jug1
            result = result | rec( l1- (c2-l2),c2);
        else         // While pouring to jug2 from jug1, jug1 ends up empty
            result= result | rec(0,l2+l1);
        if(c1-l1 <=l2)  // Similar to above cases
            result = result | rec( c1, l2-(c1-l1));
        else 
            result= result | rec(l1+l2,0);
        dp[l1][l2]=result;
        return result;
    }
    bool canMeasureWater(int x, int y, int target) {
        if (target > x + y) // Optimization for such cases
            return false;
        dp=new int*[x+1];
        for(int i=0;i<x+1;i++){
            dp[i]=new int[y+1];
            for(int j=0;j<y+1;j++)
                dp[i][j]=-1;
        }
        c1=x;
        c2=y;
        t= target;
        int ans= rec(0,0);
        for(int i=0;i<x+1;i++)  
            delete[] dp[i];
        delete[] dp;
        return ans;
    }
};
10300