//https://l...content-available-to-author-only...e.com/problems/partition-to-k-equal-sum-subsets/
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <bitset>
#include <numeric>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
template<typename T>
void print(T& container)
{
for (auto num : container)
{
cout << num << "\n";
}
cout << endl;
}
#define max_size 17
class Solution {
vector<bool> visited;
public:
bool canPartitionKSubsets(vector<int>& nums, int k)
{
// not enough nums to put atleast one in each 'k' bucket
if (nums.size() < k)
return false;
// check if it is possible to divide the total sum into k partition (bucket)
int total_sum = std::accumulate(nums.begin(), nums.end(), 0);
if (total_sum % k != 0)
return false;
visited.resize(max_size, false);
return canPartitionKSubsetsHelper(nums, visited, k, 0, 0, total_sum / k);
}
bool canPartitionKSubsetsHelper(vector<int>& nums, vector<bool>& visited, int k, int start, int currSum, int targetSum)
{
//cout << k << " " << currSum << endl;
// all 'k' buckets can be filled with the target sum
if (k == 0)
return true;
// if 'k' is filled with the target sum, recurse it for 'k-1' bucket.
if (currSum == targetSum)
return canPartitionKSubsetsHelper(nums, visited, k - 1, start, 0, targetSum);
//invalid configuration
if (currSum > targetSum)
return false;
for (int i = start; i < nums.size(); i++)
{
visited[i] = true;
if (canPartitionKSubsetsHelper(nums, visited, k, start + 1, currSum + nums[i], targetSum))
return true;
visited[i] = false;
}
return false;
}
};
int main()
{
Solution sln;
vector<int> vec = { 1, 1, 1, 1, 2, 2, 2, 2 };
cout << sln.canPartitionKSubsets(vec, 4) << endl;
return 0;
}
Ly9odHRwczovL2wuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tL3Byb2JsZW1zL3BhcnRpdGlvbi10by1rLWVxdWFsLXN1bS1zdWJzZXRzLwoKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8bnVtZXJpYz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdGVtcGxhdGU8dHlwZW5hbWUgVD4Kdm9pZCBwcmludChUJiBjb250YWluZXIpCnsKCWZvciAoYXV0byBudW0gOiBjb250YWluZXIpCgl7CgkJY291dCA8PCBudW0gPDwgIlxuIjsKCX0KCWNvdXQgPDwgZW5kbDsKfQoKI2RlZmluZSBtYXhfc2l6ZSAxNwoKY2xhc3MgU29sdXRpb24gewoJdmVjdG9yPGJvb2w+IHZpc2l0ZWQ7CnB1YmxpYzoKCWJvb2wgY2FuUGFydGl0aW9uS1N1YnNldHModmVjdG9yPGludD4mIG51bXMsIGludCBrKSAKCXsKCQkvLyBub3QgZW5vdWdoIG51bXMgdG8gcHV0IGF0bGVhc3Qgb25lIGluIGVhY2ggJ2snIGJ1Y2tldAoJCWlmIChudW1zLnNpemUoKSA8IGspCgkJCXJldHVybiBmYWxzZTsKCgkJLy8gY2hlY2sgaWYgaXQgaXMgcG9zc2libGUgdG8gZGl2aWRlIHRoZSB0b3RhbCBzdW0gaW50byBrIHBhcnRpdGlvbiAoYnVja2V0KQoJCWludCB0b3RhbF9zdW0gPSBzdGQ6OmFjY3VtdWxhdGUobnVtcy5iZWdpbigpLCBudW1zLmVuZCgpLCAwKTsKCQlpZiAodG90YWxfc3VtICUgayAhPSAwKQoJCQlyZXR1cm4gZmFsc2U7CgoJCXZpc2l0ZWQucmVzaXplKG1heF9zaXplLCBmYWxzZSk7CgkJcmV0dXJuIGNhblBhcnRpdGlvbktTdWJzZXRzSGVscGVyKG51bXMsIHZpc2l0ZWQsIGssIDAsIDAsIHRvdGFsX3N1bSAvIGspOwoJfQoKCWJvb2wgY2FuUGFydGl0aW9uS1N1YnNldHNIZWxwZXIodmVjdG9yPGludD4mIG51bXMsIHZlY3Rvcjxib29sPiYgdmlzaXRlZCwgaW50IGssIGludCBzdGFydCwgaW50IGN1cnJTdW0sIGludCB0YXJnZXRTdW0pCgl7CgkJLy9jb3V0IDw8IGsgPDwgIiAiIDw8IGN1cnJTdW0gPDwgZW5kbDsKCQkvLyBhbGwgJ2snIGJ1Y2tldHMgY2FuIGJlIGZpbGxlZCB3aXRoIHRoZSB0YXJnZXQgc3VtCgkJaWYgKGsgPT0gMCkKCQkJcmV0dXJuIHRydWU7CgoJCS8vIGlmICdrJyBpcyBmaWxsZWQgd2l0aCB0aGUgdGFyZ2V0IHN1bSwgcmVjdXJzZSBpdCBmb3IgJ2stMScgYnVja2V0LgoJCWlmIChjdXJyU3VtID09IHRhcmdldFN1bSkKCQkJcmV0dXJuIGNhblBhcnRpdGlvbktTdWJzZXRzSGVscGVyKG51bXMsIHZpc2l0ZWQsIGsgLSAxLCBzdGFydCwgMCwgdGFyZ2V0U3VtKTsKCgkJLy9pbnZhbGlkIGNvbmZpZ3VyYXRpb24KCQlpZiAoY3VyclN1bSA+IHRhcmdldFN1bSkKCQkJcmV0dXJuIGZhbHNlOwoKCQlmb3IgKGludCBpID0gc3RhcnQ7IGkgPCBudW1zLnNpemUoKTsgaSsrKQoJCXsKCQkJdmlzaXRlZFtpXSA9IHRydWU7CgkJCWlmIChjYW5QYXJ0aXRpb25LU3Vic2V0c0hlbHBlcihudW1zLCB2aXNpdGVkLCBrLCBzdGFydCArIDEsIGN1cnJTdW0gKyBudW1zW2ldLCB0YXJnZXRTdW0pKQoJCQkJcmV0dXJuIHRydWU7CgkJCXZpc2l0ZWRbaV0gPSBmYWxzZTsKCQl9CgkJcmV0dXJuIGZhbHNlOwoJfQp9OwoKaW50IG1haW4oKQp7CglTb2x1dGlvbiBzbG47Cgl2ZWN0b3I8aW50PiB2ZWMgPSB7IDEsIDEsIDEsIDEsIDIsIDIsIDIsIDIgfTsKCWNvdXQgPDwgc2xuLmNhblBhcnRpdGlvbktTdWJzZXRzKHZlYywgNCkgPDwgZW5kbDsKCXJldHVybiAwOwp9