# 474-ones-and-zeroes


Try it on <a href='https://leetcode.com/problems/474-ones-and-zeroes'>leetcode</a>

## Description
<div class="description">
<div><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>'s and </em><code>n</code><em> </em><code>1</code><em>'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>Example 1:</strong></p>

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

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> strs = ["10","0","1"], m = 1, n = 1
<strong>Output:</strong> 2
<b>Explanation:</b> The largest subset is {"0", "1"}, 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>'0'</code> and <code>'1'</code>.</li>
	<li><code>1 &lt;= m, n &lt;= 100</code></li>
</ul>
</div>
</div>

## Solution(Python)
```Python
from itertools import chain, combinations


class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        return self.topdowndp(strs, m, n)

    # Time Complexity : O(N*2^N)
    # Space Complexity: O(2^N)
    def bruteforce(self, strs: List[str], m: int, n: int) -> int:
        res = 0
        for subset in self.powerset(strs):
            zeros = sum([s.count("0") for s in subset])
            ones = sum([s.count("1") for s in subset])
            if zeros < m and ones < n:
                if len(subset) > res:
                    res = len(subset)
        return res

    def powerset(self, iterable):
        "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
        s = list(iterable)
        return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

    # Time Complexity : O(n*m*N)
    # Space Complexity: O(n*m*N)
    def topdowndp(self, strs: List[str], m: int, n: int) -> int:
        @cache
        def backtrack(m, n, i):
            if m < 0 or n < 0:
                return float("-inf")
            if i >= len(strs):
                return 0
            zero = 0
            one = 0
            for c in strs[i]:
                if c == "0":
                    zero += 1
                else:
                    one += 1
            include = 1 + backtrack(m - zero, n - one, i + 1)
            exclude = backtrack(m, n, i + 1)
            return max(include, exclude)

        return backtrack(m, n, 0)

```