Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- /*
- VERY IMPORTANT LINK -
- https://chatgpt.com/canvas/shared/68631cabdd608191b64d447a63a1ea45
- (DP + BITMASK INTUITION discussion PDF)
- */
- int getKEqualPartition(int mask, int currSum, int &targetSum, int lastIndex, int k, vector<int> &v){
- //take elements only if not used
- //start from lastIndex + 1 to generate combinations
- /// need to check if group completed or not
- for(int i = lastIndex + 1; i < v.size(); i++){
- //ensures that the current element was not used and adding it will not exceed limit of each group
- if(mask & (1 << i) == 0 && currSum + v[i] <= targetSum){
- //mark as used by setting the ith bit ON in newMask
- int newMask = mask | (1 << i);
- getKEqualPartition(newMask, currSum + v[i], targetSum, i, k, v);
- }
- }
- }
- int main() {
- // your code goes here
- int n, k;
- vector<int> v(n);
- for(int i = 0; i < n; i++){
- cin >> v[i];
- }
- cin >> k;
- int mask = 0;
- for(int i = 0; i < v.size(); i++){
- sum += v[i];
- }
- // as all the elements can't be partitioned into k parts anyways
- if(sum % k != 0){
- return 0;
- }
- //if sum can be partitioned into k parts, then each part should sum exactly to sum / k because we want every partition to be of equal sum
- else{
- sum /= k;
- }
- getKEqualPartition(mask, 0, sum, -1, k, v);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
