Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Rotate array
NonparaSign
sdefrgthyjukiujyhtg
operator++
code
shivratri
pow implementation
Test 4(2017)
Dar
Float