Partition to K Equal Sum Subsets, C++ (gcc)

Partition to K Equal Sum Subsets

class Solution {
    
    bool foo(int cur, int ind, int cnt, vector<int>& mask, const int n, const int k){
        if(cnt > k) return false;
        if(ind == mask.size()){
            if(cnt < k) return false;
            return (cur == ((1 << n) - 1));
        }
        bool ans = false;
        // take it 
        if(cur&mask[ind]);
        else{
            ans |= foo(cur|mask[ind], ind + 1, cnt+1, mask, n, k);
        }
        if(ans) return true;
        return foo(cur, ind+1, cnt, mask, n, k);
    }
    
public:
    bool canPartitionKSubsets(vector<int>& nums, int K) {
        int sum = 0, n = nums.size();
        for(auto i : nums) sum += i;
        if((sum % K) != 0) return false;
        int each = sum / K;
        
        vector<int> mask;
        for(int j = 1; j < (1 << n); j++){
            int cur_sum = 0;
            for(int k = 0; k < n; k ++)
                if((1<<k)&j) cur_sum += nums[k];
            if(cur_sum != each) continue;
            
            mask.push_back(j);
        }
        
        // for(auto i : mask) cout << i << " "; cout << endl;
        
        return foo(0, 0, 0, mask, n, K);
    }
};


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development