<p>You are given an array of binary strings <code>strs</code> and two integers <code>m</code> and <code>n</code>.</p>

<p>Return <em>the size of the largest subset of <code>strs</code> such that there are <strong>at most</strong> </em><code>m</code><em> </em><code>0</code><em>&#39;s and </em><code>n</code><em> </em><code>1</code><em>&#39;s in the subset</em>.</p>

<p>A set <code>x</code> is a <strong>subset</strong> of a set <code>y</code> if all elements of <code>x</code> are also elements of <code>y</code>.</p>

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

<pre>
<strong>Input:</strong> strs = [&quot;10&quot;,&quot;0001&quot;,&quot;111001&quot;,&quot;1&quot;,&quot;0&quot;], m = 5, n = 3
<strong>Output:</strong> 4
<strong>Explanation:</strong> The largest subset with at most 5 0&#39;s and 3 1&#39;s is {&quot;10&quot;, &quot;0001&quot;, &quot;1&quot;, &quot;0&quot;}, so the answer is 4.
Other valid but smaller subsets include {&quot;0001&quot;, &quot;1&quot;} and {&quot;10&quot;, &quot;1&quot;, &quot;0&quot;}.
{&quot;111001&quot;} is an invalid subset because it contains 4 1&#39;s, greater than the maximum of 3.
</pre>

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

<pre>
<strong>Input:</strong> strs = [&quot;10&quot;,&quot;0&quot;,&quot;1&quot;], m = 1, n = 1
<strong>Output:</strong> 2
<b>Explanation:</b> The largest subset is {&quot;0&quot;, &quot;1&quot;}, so the answer is 2.
</pre>

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

<ul>
	<li><code>1 &lt;= strs.length &lt;= 600</code></li>
	<li><code>1 &lt;= strs[i].length &lt;= 100</code></li>
	<li><code>strs[i]</code> consists only of digits <code>&#39;0&#39;</code> and <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= m, n &lt;= 100</code></li>
</ul>

class Solution {
public:
    // 3 D dp vector, as we dicused, We will give it maximum size,
    //see Constraints, 1 <= strs.length <= 600 and 1 <= m, n <= 100
    int dp[601][101][101]; 
    
    // Count one and Zero function take string as parameter and count the number of ones and zeroes present in the string and return the counts.
    pair<int, int> countOneAndZero(string s)
    {
        int one = 0, zero = 0;
        
        for(int i = 0; i < s.length(); i++) // travel in the string
        {
            if(s[i] == '1') // if == '1', then add to one
                one++;
            else            // otherwise add to zero
                zero++;
        }
        
        return {one, zero};
    }
    
    int solve(int i, int one, int zero, int& maxZero, int& maxOne, 
             vector<string>& arr)
    {
        if(i >= arr.size()) // if ith index crosses the length then return 0
            return 0;
        
        // if any of the count, crosses the criteria of having maximum one
        // or zero, then return 0
        if(one > maxOne || zero > maxZero)
            return 0;
        
        // if it is already computed, then no need to do computation again,
		//return from here itself
        if(dp[i][one][zero] != -1)
        {
            return dp[i][one][zero];
        }
        
        /* what we discused:-
        for every ith index i, we have two option, whether to include it
         in our answer or not, if include then add the count of 
         ones and zeros from that string */
        
        // pair p contains, the number of ones and zeroes present in the string of ith index of vector arr.
        pair<int, int> p = countOneAndZero(arr[i]);
        
        /* we declare three variables -
        1) ans1, If adding the count of ones and zeroes at ith index in arr,
        does not crosses our limit, then to include this in our answer.
        2) ans2, If adding the count of ones and zeroes at ith index in arr,
        does not crosses our limit, then not to include this in our answer.
        3) ansWithout, If adding the count of ones and zeroes at ith index in arr, crosses our limit, then not to include this in our answer.
        */
        
        int ans1 = 0, ans2 = 0, ansWithout = 0;
        
        // adding count of current index, not to cross our limit then-
        if(one + p.first <= maxOne && zero + p.second <= maxZero)
        {
            // ans1, including it in our answer
            ans1 = 1 + solve(i + 1, one + p.first, zero + p.second, 
                           maxZero, maxOne, arr);
            
            // not including in our answer.
            ans2 = solve(i + 1, one, zero, maxZero, maxOne, arr);
        }
        else // if crossing limit, obviously not to take
        {
            ansWithout = solve(i + 1, one, zero, maxZero, maxOne, arr);
        }
        
        // and at last return the maximum of them
        return dp[i][one][zero] = max({ans1, ans2, ansWithout});
        
        
    }
    int findMaxForm(vector<string>& arr, int m, int n) {
        // we redfine m and n as maxzero and maxOne respectively, for better clarification.
        int maxZero = m; 
        int maxOne = n;
        
        memset(dp, -1, sizeof(dp)); // intially, putting -1 in dp
        
        /* parameters of solve-
        1) First parameter is 'i', by which we move in our array of strings.
        2) Second parameter is the variable who keeps record of count of ones. (we name it as one)
        3) Third parameter is the variable who keeps record of count of zeroes. (we name it as zero)
        4) Fourth parameter is maxZero, the maximum zeros we are allowed to take.
        5) Fifth parameter is maxOne, the maximum ones we are allowed to take. 
        6) Last Sixth parameter is the array itself.
        */
        
        // return solve function
        return solve(0, 0, 0, maxZero, maxOne, arr);
    }
};
40528