LC 1655. Distribute Repeating Integers (状压)

link

class Solution {
public:
    int n;
    int memo[50][1<<10];
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        vector<int> cnt(1001);
        n=quantity.size();
        for(int i:nums) cnt[i]++;
        vector<int> freqs;
        for(int i:cnt){
            if(i>0) freqs.push_back(i);
        }
        memset(memo,-1,sizeof(memo));
        return dfs(freqs,0,0,quantity);
    }
    
    bool dfs(vector<int>& freqs, int idx, int state, vector<int>& quantity){
        if(state==( (1<<n)-1 ) ) return true;
        if(idx==freqs.size()) return false;
        
        if(memo[idx][state]!=-1) return memo[idx][state];
        bool res=dfs(freqs,idx+1,state,quantity);
        if(res){
            memo[idx][state]=1;
            return true;
        }
        for(int i=0;i<(1<<n) ;i++){
            if(i==state) continue;
            if( (state&i) !=state) continue;
            int sum=0;
            
            for(int j=0;j<n;j++){
                if( (state&(1<<j)) ==0 && (i&(1<<j))!=0){
                    sum+=quantity[j];
                }
            }
            if(sum<=freqs[idx]){
                res|=dfs(freqs,idx+1,i,quantity);
                if(res) {
                    memo[idx][state]=1;
                    return true;
                }
            }
        }
        memo[idx][state]=0;
        return false;
    }
};