<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>

from collections import Counter

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        numBinaryStrs = len(strs)
        numZeros, numOnes = m, n

        """
        Given that most likely we will see similar binary strings, intuition is that we can solve using top down recursive approach
        Sort the strs based on length of binary string, add all the strs that can be added
        """
        cache = dict()
        def dfs(i, remainOnes, remainZeros):
            # Base Case - Iterated over all the binary strings
            if i >= numBinaryStrs:
                # Return 0 because we no longer have any strings to add to the result
                return 0
            # BC2 - Maybe if we saw a similar result in cache
            if (i, remainOnes, remainZeros) in cache:
                return cache[(i, remainOnes, remainZeros)]

            # Recursive Case - For current string, Check if including or excluding it will result in a larger subset
            freqMap = Counter(strs[i])
            countOnes = freqMap['1']
            countZeros = freqMap['0']
            
            # Choosing not to include currStr as part of subset is something we can do each time
            cache[(i, remainOnes, remainZeros)] = dfs(i+1, remainOnes, remainZeros)

            # Can only count this as part of subset if there are enough remaining 1 and 0s to support it
            if countOnes <= remainOnes and countZeros <= remainZeros:
                # Check if include or exclude results in a higher val
                # Include will +1 since we include a string
                cache[(i, remainOnes, remainZeros)] = max(1 + dfs(i+1, remainOnes - countOnes, remainZeros - countZeros), cache[(i, remainOnes, remainZeros)])

            return cache[(i, remainOnes, remainZeros)]

        return dfs(0, numOnes, numZeros)

117218