***Brief note about Question-***\n* We have to return the size of the largest subset of strs such that there are at most `m 0\'s `and` n 1`\'s in the subset.\n```\nLet\'s take an example not given in the question- \nSuppose our arr is arr[]: ["101", "111", "000", "01", "111110100"], \n Given, m = 5 and n = 6\n\t\t\t\t \nNow, This says that we can include at most 5 zeroes and at most 6 ones in our ans,\nSo, we say that we will choose "101", "111", "000", and "01"\nby choosing this, we satisy our criteria of atmost 5 zeroes and 6 ones,\nso the answer is 4.\n\nOne thing is to notice here is that we have to choose atmost,\nmeans maximum we can choose for zero is \'m\' and maximum we can choose for one is \'n\'.\nWe have option to choose less than \'m\' and \'n\' but to maximise the count of subset.\n```\n____________________________\n***Generating intiutaion:***\n* First thing that we will see is that from the given array of strings we have to choose some of its indices,such that after choosing them we will count our ones and zeros.\n\n* So, this is kind of ***option type thing***, suppose we start traversing in our given vector, and stand on any ith index, then for that index we have a choice.\n* And **what choice** is that? Choice is that we will ask a question to ourself whether to include this string in our answer or not.\n* ***So, if we decide to choose this string in our answer then we will add count of ones and zeroes of this string in our answer and move ahead and if we decide not to include this string in our answer, then we will do nothing, we just move forward.***\n* So, Overall we can say that we have choice for every index of array whether to include it our answer or not to include.\n* And whenver we heard a term that here we have a choice like this, then we will say **recursion** will use here.\n* **Why recusrion?** Recursion is because it will try out every single possibility for every string in our answer.\n* Let see ahead with a example.\n__________________________\n***Again a example for better understanding:***\n```\nWe will take a very light example, \nSuppose array given to us is as arr[]: ["00", "1","0", "000", "11"], Given m = 3 and n = 2\nIt says that we can choose atmost three zeroes (m = 3) and also we can choose atmost two ones(n = 2)\n\nSee here, we can say that we have to choose three zeroes, so what are the options or to say \nwhat are the choices we have,\nWe have a option in which we will say for zeroes we will choose "000", it complete our criteria\nof having atmost three zeroes and give us the count of subset as 1.\n\nBut, since we want to maximise our answer, we will say that it is better to choose "00" and "0",\nit also satisfies our criteria of having atmost three zeroes, but with the count of subset as 2.\n\nSo, we saw here we will have choice for every string in our array, whether to include this in our answer or not.\n_______________________________________________________________________________________\n\n Visuliaze something like this, arr[]: ["00", "1","0", "000", "11"]\n\t / \\\n\t\t\t\t\t\t\t\t\t\t\t / \\\n\t\t\t whether to choose this whether to not choose this\n\t\t\t\t\t\t {Same for all other strings}\n\t\t\t\t\t\t\t\t \nAnd that is what we are going to implement.\n```\n__________________________________________\n***Now What?***\n* Now till here we understand that ok we have option for every string in our array. Now what?\n* We will ***keep a record of count ones and zeroes***.\n* We say when we decide to include this string in our answer, then we add count of ones and zeroes of this string in our answer and then move to anthor index.\n* But if we decide not to choose this, so we do not do any change in our counts, because we are not choosing this.\n* And also, on including a string in our anwer we will see whether after including this in our answer our criteria of having atmost m zeroes and n zeroes are satisfied or not.\n* If it crosses that criteria then we will do nothing we simply move ahead.\n* But if it not crosses then criteria, then we will apply our option that whether to choose this in our answer.\n* See commented code for more explanation.\n\n* We will move further with first recursion and then memoziation.\n___________________________ \n***Solution - I (Recursion, TLE)-***\n```\nclass Solution {\npublic:\n // 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.\n pair countOneAndZero(string s)\n {\n int one = 0, zero = 0;\n \n for(int i = 0; i < s.length(); i++) // travel in the string\n {\n if(s[i] == \'1\') // if == \'1\', then add to one\n one++;\n else // otherwise add to zero\n zero++;\n }\n \n return {one, zero};\n }\n \n int solve(int i, int one, int zero, int& maxZero, int& maxOne, \n vector& arr)\n {\n if(i >= arr.size()) // if ith index crosses the length then return 0\n return 0;\n \n // if any of the count, crosses the criteria of having maximum one\n // or zero, then return 0\n if(one > maxOne || zero > maxZero)\n return 0;\n \n /* what we discused:-\n for every ith index i, we have two option, whether to include it\n in our answer or not, if include then add the count of \n ones and zeros from that string */\n \n // pair p contains, the number of ones and zeroes present in the string of ith index of vector arr.\n pair p = countOneAndZero(arr[i]);\n \n /* we declare three variables -\n 1) ans1, If adding the count of ones and zeroes at ith index in arr,\n does not crosses our limit, then to include this in our answer.\n 2) ans2, If adding the count of ones and zeroes at ith index in arr,\n does not crosses our limit, then not to include this in our answer.\n 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.\n */\n \n int ans1 = 0, ans2 = 0, ansWithout = 0;\n \n // adding count of current index, not to cross our limit then-\n if(one + p.first <= maxOne && zero + p.second <= maxZero)\n {\n // ans1, including it in our answer\n ans1 = 1 + solve(i + 1, one + p.first, zero + p.second, \n maxZero, maxOne, arr);\n \n // not including in our answer.\n ans2 = solve(i + 1, one, zero, maxZero, maxOne, arr);\n }\n else // if crossing limit, obviously not to take\n {\n ansWithout = solve(i + 1, one, zero, maxZero, maxOne, arr);\n }\n \n // and at last return the maximum of them\n return max({ans1, ans2, ansWithout});\n \n \n }\n int findMaxForm(vector& arr, int m, int n) {\n // we redfine m and n as maxzero and maxOne respectively, for better clarification.\n int maxZero = m; \n int maxOne = n;\n \n /* parameters of solve-\n 1) First parameter is \'i\', by which we move in our array of strings.\n 2) Second parameter is the variable who keeps record of count of ones. (we name it as one)\n 3) Third parameter is the variable who keeps record of count of zeroes. (we name it as zero)\n 4) Fourth parameter is maxZero, the maximum zeros we are allowed to take.\n 5) Fifth parameter is maxOne, the maximum ones we are allowed to take. \n 6) Last Sixth parameter is the array itself.\n */\n \n // return solve function\n return solve(0, 0, 0, maxZero, maxOne, arr);\n }\n};\n```\n__________________________________________________\n***Solution - II (Memoziation, Accepted)-***\n* In memoziation, we make an dp array, to store some already previous computed result.\n* ***How many parameter are there which are changing?***\n* We will see, first index itself and then count of ones and and zeroes.\n* So, we will a 3 D vector for storing results that are already previous computed.\n* See, code :)\n```\nclass Solution {\npublic:\n // 3 D dp vector, as we dicused, We will give it maximum size,\n //see Constraints, 1 <= strs.length <= 600 and 1 <= m, n <= 100\n int dp[601][101][101]; \n \n // 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.\n pair countOneAndZero(string s)\n {\n int one = 0, zero = 0;\n \n for(int i = 0; i < s.length(); i++) // travel in the string\n {\n if(s[i] == \'1\') // if == \'1\', then add to one\n one++;\n else // otherwise add to zero\n zero++;\n }\n \n return {one, zero};\n }\n \n int solve(int i, int one, int zero, int& maxZero, int& maxOne, \n vector& arr)\n {\n if(i >= arr.size()) // if ith index crosses the length then return 0\n return 0;\n \n // if any of the count, crosses the criteria of having maximum one\n // or zero, then return 0\n if(one > maxOne || zero > maxZero)\n return 0;\n \n // if it is already computed, then no need to do computation again,\n\t\t//return from here itself\n if(dp[i][one][zero] != -1)\n {\n return dp[i][one][zero];\n }\n \n /* what we discused:-\n for every ith index i, we have two option, whether to include it\n in our answer or not, if include then add the count of \n ones and zeros from that string */\n \n // pair p contains, the number of ones and zeroes present in the string of ith index of vector arr.\n pair p = countOneAndZero(arr[i]);\n \n /* we declare three variables -\n 1) ans1, If adding the count of ones and zeroes at ith index in arr,\n does not crosses our limit, then to include this in our answer.\n 2) ans2, If adding the count of ones and zeroes at ith index in arr,\n does not crosses our limit, then not to include this in our answer.\n 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.\n */\n \n int ans1 = 0, ans2 = 0, ansWithout = 0;\n \n // adding count of current index, not to cross our limit then-\n if(one + p.first <= maxOne && zero + p.second <= maxZero)\n {\n // ans1, including it in our answer\n ans1 = 1 + solve(i + 1, one + p.first, zero + p.second, \n maxZero, maxOne, arr);\n \n // not including in our answer.\n ans2 = solve(i + 1, one, zero, maxZero, maxOne, arr);\n }\n else // if crossing limit, obviously not to take\n {\n ansWithout = solve(i + 1, one, zero, maxZero, maxOne, arr);\n }\n \n // and at last return the maximum of them\n return dp[i][one][zero] = max({ans1, ans2, ansWithout});\n \n \n }\n int findMaxForm(vector& arr, int m, int n) {\n // we redfine m and n as maxzero and maxOne respectively, for better clarification.\n int maxZero = m; \n int maxOne = n;\n \n memset(dp, -1, sizeof(dp)); // intially, putting -1 in dp\n \n /* parameters of solve-\n 1) First parameter is \'i\', by which we move in our array of strings.\n 2) Second parameter is the variable who keeps record of count of ones. (we name it as one)\n 3) Third parameter is the variable who keeps record of count of zeroes. (we name it as zero)\n 4) Fourth parameter is maxZero, the maximum zeros we are allowed to take.\n 5) Fifth parameter is maxOne, the maximum ones we are allowed to take. \n 6) Last Sixth parameter is the array itself.\n */\n \n // return solve function\n return solve(0, 0, 0, maxZero, maxOne, arr);\n }\n};\n```\n_______________________________\n* **Note:** I am not providing bottom up soln, because every second post is that itself.\n* Main thing is to come up with recursive approach and then memoize it.\n______________\n***`If u find this useful , please consider to give a upvote!!`***

Ones and Zeroes

Problem Description

Problem Description

Answer Panel