why my DFS solution is not correct?


  • 0
    J
    struct node
    {
        int ones;
        int zeros;
        node(string s)
        {
            int _ones = 0;
            int _zeros = 0;
            for(int i = 0;i<s.size();i++)
                if(s[i]=='1')_ones++;
                else _zeros++;
            ones = _ones;
            zeros = _zeros;
        }
    };
    
    class Solution {
    public:
        int findMaxForm(vector<string>& strs, int m, int n) {
            vector<node>nums;
            for(auto str:strs) 
            {
                node curr(str);
                nums.push_back(curr);
            }
            int res=0;
            dfs(nums,0,0,m,n,0,res,0);
            return res;
           
        }
    private:
        void dfs(vector<node>nums,int zeros,int ones,int m,int n,int idx,int& res,int k)
        {
            if(zeros>m||ones>n) return;
            if(zeros==m && ones == n)
            {
                res = max(res,k);
                return;
            }
            for(int i = idx;i<nums.size();i++)
            {
                k++;
                dfs(nums,zeros+nums[i].zeros,ones+nums[i].ones,m,n,i+1,res,k);
                k--;
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.